Jednocześnie postanowiono, że szkielet drużyny będzie opierać się na zawodnikach pochodzących z regionu tyrolskiego. Decyzja pozytywnie wpłynęła na wyniki zespołu – już w pierwszym sezonie drużyna zwyciężył w sezonie zasadniczych tych rozgrywek, by w fazie play-off ulec jedynie Dornbirner EC. Rok później postanowiono zmienić system rozgrywek Nationalligi. Sezon zasadniczy składał się z dwóch rund. W pierwszej Rekiny zwyciężyły i na początku drugiej rundy otrzymali cztery punkty do tabeli rozgrywek (drugi zespół dostał trzy punkty, trzeci dwa, czwarty jeden). W tej fazie rozgrywek zespół zwyciężył jedynie w trzech spotkaniach (dwa w regulaminowym czasie gry) i zajął trzecie miejsce, które dało awans do play-off. W ćwierćfinale EHC Lustenau, jednak w półfinale w serii do trzech zwycięstw w decydującym spotkaniu ulegli VEU Feldkirch. W następnym sezonie drużyna po raz pierwszy w historii zdobyła mistrzowski tytuł Nationalligi. W fazie play-off Innsbruck przegrał jedynie jedno spotkanie (na 10 rozegranych), pokonując bez porażki w finale Dornbirner EC.