Про життя цього святого, покровителя мандрівників і заступника за душі повішеників, відомо не так багато, як про його смерть і посмертя.
Згідно з його життєписом, складеним за 30 років після смерті, Коломан був ченцем ірландського чи шотландського походження, можливо навіть княжого чи королівського роду. Пізніша традиція навіть називала його сином Маела Сехнайлл мак Домнайлла, верховного короля Ірландії на межі Х-ХІ століть, однак реальних доказів цього немає.
1012 року Коломан вирушив у паломництво до Святої Землі, яке за волею Божого перетворилося на паломництво до Небесного Єрусалима. Його шлях пролягав через землі сучасної Австрії, які у той час були полем постійних битв між австрійськими, моравськими і богемськими військами.
Самотній незнайомець, який зовсім не розмовляв німецькою мовою, одразу викликав підозру віденців. Його затримали і звинуватили у тому, нібито він моравський шпигун. Оскільки довести протилежне Коломан ніяк не міг, його жорстоко катували, а потім повісили на бузині — поруч із двома страченими злодіями. Після його загибелі тіло Коломана залишили висіти на дереві — як попередження іншим.
З цього моменту почалися чудеса. Тіло Коломана провисіло на бузині 18 місяців — і за цей час не зазнало жодних ознак тління. Навіть птахи і дикі звірі оминали його; натомість люди почали розповідати про чудеса, що відбувалися на місці загибелі нікому не відомого ченця.
За деякий час чутки про повішеника-чудотворця дійшли до Церкви. Його зняли з дерева і поховали у базиліці в Штокерау, а у 1014 році маркграф Австрії Генріх І звелів відкрити гробницю Коломана і побачив, що його тіло залишається нетлінним. Після цього останки святого перевезли у Мельк (Австрія), де воно було з почестями поховане в бенедиктинському абатстві на Дунаї.
Святий Коломан залишався єдиним покровителем Австрії аж до 1633 року, після чого поступився першістю святому Леопольду. Його гробниця стала загальновизнаним місцем чудес, і четверо Пап дарували відпусти тим, хто звершував паломництво, щоби просити його про заступництво. День його спомину — 17 липня, в Австрії також 13 жовтня, у день перенесення реліквій.