Aus einer Salzburger Organistenfamilie stammend, war H. zeit seines Lebens den Habsburgern eng verbunden. Bereits in jungen Jahren gelangte er an den Hof Friedrichs III., wo er seine musikalische Ausbildung erfuhr. 1478 ging er mit dessen Neffen Erzherzog Sigmund nach Innsbruck und erlangte 1480 eine Lebensstellung als Hoforganist. 1490 kam er in den Dienst von Maximilian I., der einen Teil der Innsbrucker Hofmusikkapelle übernahm. Als „obrigster organist“ des Kaisers war H. damit am Höhepunkt seiner Karriere angelangt. Sein Ruhm als Orgelspezialist und Lehrer strahlte bald weit über die Grenzen des Landes, er galt als bedeutendster Organist seiner Zeit, der v. a. auch durch seine Improvisationskunst beeindruckte. In der berühmten Darstellung des Triumphzugs Kaiser Maximilians von Hans Burgkmair wird H. ein eigener Wagen mit Regal und Positiv zugestanden (s. Abb.), 1515 wurde er sogar zum Ritter geschlagen. Zu den zahlreichen Schülern, den „Paulomimen“, zählte u. a. W. Grefinger. Mit dem Wechsel in die Hofkapelle Maximilians begann auch eine reiseintensive Zeit. 1498 ließ sich H. in Passau nieder, ab 1507 war er in Augsburg/D ansässig, wo er bis spätestens 1520 wohnhaft blieb. In dieser Lebensphase dürften auch die meisten erhaltenen Lieder entstanden sein, die vielfach in zeitgenössischen Augsburger Quellen überliefert sind. Der Tod des Kaisers und die Auflösung der Hofkapelle 1519 führten zwangsläufig auch zu einer Neuorientierung im Leben H.s. Möglicherweise nach einer kurzen Zwischenstation in Passau fand er spätestens ab 1522 eine neue Position in Salzburg, wo er auch den Lebensabend verbrachte. Sein letzter Dienstgeber war der neue Erzb., Kardinal Matthäus Lang. Neben seinen Orgeldiensten am Salzburger Dom entstand in den letzten Jahren eine Sammlung von humanistisch geprägten Odenkompositionen (Humanismus), die als Harmoniae poeticae 1539 posthum in Druck gingen. In den Salzburger Jahren ergab sich neben der Bekanntschaft mit H. Finck auch persönlicher Kontakt zu Paracelsus, der den Organisten H. mit Albrecht Dürer in der Malerei verglich.