Trudną sytuację Macieja wykorzystywali również możnowładcy, którzy zapewnili sobie obowiązek zwoływania co rok sejmu, stworzenie armii najemnej, finansowanej ze skarbu królewskiego i nienakładania na szlachtę podatków.
Początek rządów mały|Rzeźba młodego króla Macieja Korwina W pierwszym okresie panowania, do około roku 1465, głównym celem władcy było zapewnienie niepodległości państwa, utrzymanie władzy nad całością terytorium oraz umocnienie podupadłej władzy królewskiej. Próby umocnienia pozycji króla spotkały się jednak z oporem możnowładców, w tym palatyna Władysława Garai, którego zdjął z urzędu. Pozbył się swojego wuja, Mihályego Szilágyiego (podczas wyprawy na Turków podczas której dostał się do niewoli i w wyniku braku uiszczenia okupu został stracony w Konstantynopolu), który wcześniej przeszedł na stronę Habsburgów i uznał Fryderyka III za króla Węgier. Maciej zdołał pokonać magnatów i zmusić wojska habsburskie do wycofania się z kraju przy pomocy wojsk zaciężnych i dawnych stronników ojca oraz dzięki poparciu ze strony miast i średniej szlachty. W 1465 roku zmarła jego żona Katarzyna z Podiebradów, co przyczyniło się do bardziej agresywnej polityki wobec królestwa Czech.