Die Legenden berichten Unterschiedliches über den heiligen Koloman: Er soll ein irischer Königssohn oder Wanderprediger gewesen sein; der zeitgenössische Chronist Thietmar von Merseburg bezeichnete ihn als „Pilger“. Jedenfalls war er ein Fremder, der mit eigentümlichem Aussehen und unverständlicher Sprache den Argwohn der Einheimischen hervorrief, als er im Jahr 1012 durch Stockerau bei Wien zog. In der Annahme, er sei ein böhmischer Spion, wurde er festgenommen, gefoltert und an einem dürren Holunderbaum erhängt.
Bereits Thietmar schildert, wie der Baum als Zeichen der Heiligkeit Kolomans alsbald zu blühen begonnen haben soll. Auch sei der Leichnam, den man längere Zeit an dem Ast hängen ließ, nicht ver-west – für die Zeitgenossen ein untrügliche Zeichen der Heiligkeit. Koloman wurde in der Kirche zu Stockerau beigesetzt, wo sich die Wunder an seinem Grab mehrten, was immer mehr Pilger und Hilfesuchende anzog. Auch der Babenberger Markgraf Heinrich I. hörte davon. Als auf sein Geheiß hin das Grab in Stockerau geöffnet wurde, fand man, so heißt es, den Leichnam Kolomans völlig unversehrt vor. Der Markgraf ließ Koloman in die Babenberger-Residenz Melk überführen, wo er am 13. Oktober 1014 in der dortigen Peterskirche beigesetzt wurde. Dieser offizielle Akt kam im 11. Jahrhundert einer formellen Heiligsprechung gleich. Der heilige Koloman blieb eng mit der Geschichte Melks und ganz Österreichs verbunden.
