Mátyás központosított királyi hatalmat épített ki, amelynek alapját az első magyar állandó zsoldoshadsereg, a fekete sereg képezte. Célja egy ütőképes, csak tőle függő haderő felállítása volt. Az aránylag drága zsoldos hadsereg kialakításához az 1460-as években fogott hozzá. A 15 ezer fős állandó zsoldoshadsereg óriási kiadást jelentett. A magvát a cseh huszita harcosok képezték. A sereg négy fő fegyvernemben alakult ki: a nehézlovasság, a dunai hajóhad, a gyalogság és a tüzérség. E sereget csak Mátyás király halála után kezdték „fekete seregnek" nevezni, valószínűleg a Mátyás temetésekor viselt fekete szalag miatt.

Kinizsi Pál apja a legenda szerint egy molnár volt, aki már harcolt Hunyadi János hadseregében a törökök ellen. Kinizsi Pál a morvaországi hadjáratban tűnt fel. 1479-ben egy 35-40 ezer fős török sereg tört be Magyarországra, és feldúlta Szászföldet. Kinizsi Pál Báthory István erdélyi vajdával együtt 1479-ben Kenyérmezőnél hatalmas győzelmet aratott a török sereg felett. Később Mátyás király a déli végek védelmével bízta meg. Mátyás király íránt tanúsított hűségéért megkapta a Budáról Itáliába vezető út mentén fekvő Vázsony várát („Kinizsi várat"), a hozzá tartozó birtokokkal.