Ushtria e parë kryqtare e organizuar nga Selia e Shenjtë arriti në kufijtë e Hungarisë në shtator 1096. Ajo drejtohej nga Godfrey of Bouillon, Duka i Lorenës së Poshtme.Godfrey dërgoi një kalorës i cili tashmë ishte i njohur për Coloman për të filluar negociatat për hyrjen e kryqtarëve në Hungari.Tetë ditë më vonë, Coloman ra dakord të takohej me Godfrey në Sopron.Mbreti i lejoi kryqtarët të marshonin nëpër mbretërinë e tij, por vendosi që vëllai më i vogël i Godfrey, Baldwin dhe familja e tij të qëndronin me të si pengje.Kryqtarët kaluan nëpër Hungari në mënyrë paqësore përgjatë bregut të djathtë të Danubit;Coloman dhe ushtria e tij i ndoqën në bregun e majtë.Ai i liroi pengjet e tij vetëm pasi të gjithë kryqtarët kishin kaluar lumin Sava, i cili shënonte kufirin jugor të mbretërisë.Marshimi i pandërprerë i ushtrisë kryesore të kryqëzatave nëpër Hungari krijoi reputacionin e mirë të Coloman në të gjithë Evropën.