Ersten Musikunterricht erhält Heinrich Fidelis bei dem Fuldaer Musiker Michael Henkel (1780-1851). Michael und später sein Sohn Georg Andreas Henkel (1805-1871) unterrichten Heinrich Fidelis Müller in den Schulen. Darüber hinaus erhält er wohl auch bei ihnen Klavier- und Orgelunterricht. Sicher sind sie auch verantwortlich für seine Einführung in die Grundlagen des Tonsatzes und der Komposition.

Jedenfalls fällt schon früh auf, dass Heinrich Fidelis nicht nur außerordentlich musikalisch ist, sondern auch, dass er andere zum Mitsingen und zum gemeinsamen Musizieren begeistern kann. Als 16jähriger ist es seine Aufgaben, mit seinen Mitschülern Lieder einzustudieren und ihren Gesang am Flügel zu begleiten. Solche Gesangsübungen sind eine pädagogische Neuerung des 19. Jahrhunderts und eng an den neu aufkommenden Sportunterricht angeschlossen. Außerdem wirkt Heinrich Fidelis als Sänger im Fuldaer Gesangverein „Caecilia“ mit und tritt bisweilen auch als Solist auf.

Dommusik in Fulda

Entsprechend den seit dem Konzil von Trient (1545-1563) für die Ausbildung aller katholischen Priester verbindlichen Richtlinien absolviert Müller von 1856 bis 1859 sein Theologiestudium im Fuldaer Priesterseminar. Die Fuldaer Dommusik war zu dieser Zeit in einem außerordentlich desolaten Zustand. Die Aufführung von großen Orchestermessen war in Fulda insbesondere seit der Barockzeit fester Bestandteil der fürstbischöflichen Liturgie gewesen. Bis Mitte des 19. Jahrhunderts wurde diese Praxis aber inhaltlich und formal immer stärker kritisiert: der Standort der Musiker auf der Orgelempore in großer Entfernung vom Altar beeinträchtigte die Verständlichkeit und Qualität der musikalischen Darbietungen erheblich. Doch im Laufe des 19. Jahrhunderts verlangte man genau dies immer mehr. Verständlichkeit, an alten Kirchenliedern orientierte Kantionalsätze – sie standen nun hoch im Kurs. „Der Choral in seiner vierstimmigen Aufführung durchdringt Mark und Bein, stimmt zur Andacht, erhebt das Gemüt, denn er ist kirchlich und bewährt“ urteilt der Fuldaer Dompfarrer Schmitt schon 1852. Dommusikdirektor Henkel legt daraufhin in diesem Jahr sein Amt nieder. Bis 1867 existiert in Fulda kein Domchor mehr; lediglich Knaben aus dem bischöflichen Konvikt am Priesterseminar übernehmen, so gut es geht, den Sängerdienst in der Bischofskirche.