Eishockey hat in der Dreiflüssestadt Passau mehr Tradition als man vermuten möchte: Schon in den 50er Jahren wurde Eishockey in Passau in einer Verbandsrunde gespielt. Auf Natureis zu spielen wurde jedoch immer schwieriger, und so endete die Ära des damaligen ERC Passau mit einer 19:0 Niederlage in Straubing in der Saison 64/65. 1965 war es, als sich der ERC Passau aus der Eishockey-Bezirksliga zurückzog, weil der Betrieb einer Natureis-Bahn zu aufwendig wurde. Der Verein löste sich schließlich auf und über drei Jahrzehnte lang war Passau ein weisser Fleck auf der deutschen Eishockey-Landkarte.

Die EHF Passau Black Hawks e.V. wurden am 19.12.1997 offiziell aus der Taufe gehoben. Zwei Eishockeyhobbymannschaften - die "Patriching Black Hawks" und "EHF Passau Wölfe" - fusionierten und gründeten einen eingetragenen Verein.
Mit der Eröffnung der Passauer Eis-Arena im November 2003 begann für den Verein eine neue Zeitrechnung. Der EHF Passau startette in der Saison 03/04 in der Bezirksliga Bayern, Gruppe Ost und wurde sofort Bezirksligameister, wodurch man in die Landesliga aufstieg.
In der Landesliga-Saison 04/05 erreichte man die Qualifikationsrunde, scheiterte dort jedoch an den Memminger Indians, welche in die Bayernliga aufstiegen. Den Bayernliga-Aufstieg schaffte der EHF in der Saison 05/06, wo man im Finale auch den Mitaufsteiger EC Ulm/Neu-Ulm 2000 besiegte. Außerdem holte man sich in dieser Saison den Bayernkrug-Pokal.
Die Saison 06/07 verlief für die Black Hawks sehr erfolgreich. Nach Ende der Vorrunde belegte man den 1. Platz. In den Play-Offs kam man bis ins Finale, besiegte dort den Deggendorfer SC und holte sich den Meistertitel. Gleichzeitig stieg man (zusammen mit Deggendorf) in die Oberliga auf.