En realidad, los Kinizsi eran de origen serbio y el padre de Pablo ya había luchado junto al regente húngaro Juan Hunyadi contra los turcos otomanos invasores.
Por su gran lealtad, Kinizsi recibió en 1472 la ciudad de Vázsony y los territorios circundantes.
A partir de este momento ésta fue conocida como la fortaleza Kinizsi, la cual fue transformada internamente en un lujoso palacio.
Luego de la muerte del rey Matías en 1490, Kinizsi apoyó al nuevo pretendiente del trono Vladislao II de Hungría, y se enfrentó a Juan Corvino, el hijo ilegítimo del rey, al cual derrotó en el campo de batalla y persuadió para que no reclamase el trono húngaro.
En 1492 eliminó los restos del desmembrado Ejército Negro de Hungría, que alguna vez había servido al fallecido rey Matías.