О жизни св. Коломана известно крайне мало (житие было написано через 30 лет после его гибели). Считается, что он происходил из ирландского или шотландского княжеского рода, и был убит по дороге в Иерусалим 17 июля 1012 возле Штоккерау. В это время Австрия была полем войны между императором Генрихом Святым и польским князем Болеславом Храбрым. Коломан, не знавший немецкого языка, попал в руки одной из воюющих партий, был принят за шпиона-чеха, и после мученических пыток повешен на бузине, между двух разбойников. Тело Коломана, принятого за преступника, по тогдашнему обычаю не было похоронено, и в течение полутора лет не подверглось разложению. Чудеса, связанные с покойным, заинтересовали церковь, и он был захоронен с почестями в базилике Штоккерау.
В 1014 году Генрих I (маркграф Австрии) также заинтересовался почитаемым в народе Коломаном и устроил вскрытие склепа Коломана в Штокерау; мощи вновь оказались нетленными. 13 октября 1014 Генрих перезахоронил их в Мельке. Маркграф Фридрих II, добивавшийся учреждения в своих владениях епископской кафедры, организовал написание Страстей св. Коломана и поощрял народный культ Коломана — национальный святой был важным подспорьем в его политике. В 1244 — папа Иннокентий IV канонизировал святого и повелел Фридриху II отмечать день памяти Коломана по всем австрийским землям. Старейшая церковь, названная в память о святом, датирована XIII веком и находится в Лаб-им-Вальде.
После смерти Фридриха король венгерский потребовал мощи св. Коломана себе, и получил их, однако в итоге вернул их в Мельк, так как духовенство предрекло вымогателю стихийные бедствия. Тело Коломана оказалось в Мельке, череп без нижней челюсти — в Секешфехерваре, а челюсть исчезла без следа. Она «чудесно обрелась» в 1752 году и с тех пор демонстрируется верующим раз в год, 13 октября.
В 1362 Рудольф IV (герцог Австрии) выстроил над склепом в Мельке роскошное надгробие, а в венском соборе св. Стефана появилась вторичная реликвия — так называемый Коломанов камень (нем. Kolomanistein), на котором бронзовыми буквами выложена похвала святому. Вероятно, Рудольф планировал перенос мощей в Вену. Этот перенос не состоялся; в последний раз мощи были потревожены при перестройке мелькского замка.
Коломан был единственным святым — покровителем Австрии с 1244 по 1663 (в 1663 первенство было передано Святому Леопольду). Святой Коломан — покровитель Штоккерау, Мелька и монастыря Мельк. В иконографии — изображается в обличье паломника, нередко — повешенным или с петлёй в руке.