Nach Abschluss seiner Gesangsausbildung am Konservatorium der Stadt Wien studierte Holecek an der Akademie für Musik und darstellende Kunst. Zu seinen Gesangslehrerinnen dort gehörte unter anderem Elisabeth Radó. Sein Debüt hatte er 1960 an der Volksoper als Papageno in der Zauberflöte. In derselben Rolle war er 1962 erstmals an der Wiener Staatsoper zu hören, und ab 1965 trat er in beiden Häusern auf. Holecek gastierte unter anderem an den Opernhäusern in Paris, Barcelona, Rom, Stockholm, Stuttgart, Zürich, München, Hamburg, Berlin und auch bei den Bregenzer Festspielen.
Holecek interpretierte viele Operettenrollen, allein in der Fledermaus spielte er die Rollen des Falke, Frank und des Frosch. Er war auch als Intendant und Regisseur bei den Sommerfestspielen auf der Schallaburg und bei den Kamptaler Festspielen aktiv.[3] Darüber hinaus wirkte er bei einer Vielzahl von Ton- und Schallplattenaufnahmen sowie Fernsehproduktionen mit und hatte zahlreiche eigene TV-Shows, wobei vor allem seine Parodien beim Publikum sehr beliebt waren.
Holecek widmete sich auch mit Nachdruck der Pflege des Wienerliedes. Gemeinsam mit Heinz Zednik und den Philharmonia-Schrammeln sowie mit dem Wiener Schrammel Ensemble gestaltete er mehrere CD-Einspielungen. Tourneen mit Wienerliedern führten ihn nach Los Angeles, Montreal, Moskau und Japan. Holecek war wohl der größte Papageno des 20. Jahrhunderts.
Außerdem war Holecek ehrenamtliches Vorstandsmitglied des Wiener Tierschutzvereins. Sein Sohn Sebastian Holecek wurde ebenfalls Sänger.
Heinz Holecek verstarb im April 2012 an seinem 74. Geburtstag, nachdem er seit einem Zusammenbruch im Februar im Koma gelegen hatte.[4] Er wurde unter großer Anteilnahme am 27. April 2012 auf dem Neustifter Friedhof (1-10-7) in Wien beigesetzt.
Johann Strauß: Die Fledermaus. Mit Eberhard Waechter, Gundula Janowitz, Wolfgang Windgassen, Waldemar Kmentt, Heinz Holecek (Falke), Erich Kunz, Otto Schenk. Dirigent: Karl Böhm, Wiener Philharmoniker, Fernseh-Verfilmung (1972)
