Podczas pierwszej wyprawy krzyżowej w tym samym 1096 r. zmuszony był stawić czoła problemowi krzyżowców przebywających królestwo węgierskie w drodze do Ziemi Świętej. Początkowo wszystko przebiegało bez incydentów. Pierwsza grupa zmierzająca do Jerozolimy północnym szlakiem przez Węgry, dowodzona przez Waltera Bez Mienia wyruszyła natychmiast po Świętach Wielkanocnych, prawdopodobnie w pierwszy wtorek (15 kwietnia 1096) i do granicy węgierskiej dotarła w dniu 8 maja. Wysłano gońców do Kolomana z prośbą o zezwolenie na przemarsz i pomoc w uzyskaniu żywności dla ludzi Waltera. Koloman odniósł się do prośby życzliwie i zezwolił wojskom na przebycie kraju. Z końcem miesiąca znalazły się one w Zemuniu, na południowej granicy królestwa, i po przeprawie w Belgradzie przez Sawę wkroczyły do Bizancjum.