V rokoch 1411 – 1413 úspešne bojoval vo vojne proti Benátkam, kde dokonca velil Stiborovým oddielom.

Jeho rozhodnutie vstúpiť do služieb vojvodu sa ukázalo ako správne – provinčný šľachtic sa totiž postupne dostal do spoločnosti najvplyvnejších ľudí vtedajšieho feudálneho Uhorska...

Keď v roku 1414 Stibor zo Stiboríc zomrel, Albert vstúpil do služieb jeho synovca – jágerského biskupa Stibora.

Ďalšie veľké zmeny v jeho živote priniesla účasť na koncile, ktorý sa začal v roku 1414 v nemeckej Kostnici, blízko dnešných švajčiarskych hraníc. Do mesta sa dostal zrejme v sprievode svojho nového pána – jágerského biskupa. A opäť ho tu postretlo šťastie, lebo Žigmund Luxemburský mu v roku 1417 udelil hodnosť priora Vrany, čím sa stal najvyšším predstaviteľom johanitského rádu v Uhorsku. Zo strany panovníka išlo o prejav veľkej priazne a dôvery, pretože panovník nemal s odbojným rádom johanitov dobré skúsenosti...

Johaniti boli členmi pôvodne jeruzalemského cirkevného rytierskeho Rádu svätého Jána a ich predstaviteľom v Uhorsku bol prior, sídliaci na chorvátskom hrade Vrana (prior Aurane).

Vstupom do rádu sa Albert z Michaloviec musel zriecť určitých stránok svetského života – v tom čase bol už vdovcom, pričom mal niekoľko detí (Jána, Ladislava a Juraja).