En 1977, il participe à la fondation du Vienna Art Orchestra, dont il est un des principaux solistes jusqu'à son départ en 1989[1],[2].
Au milieu des années 1980, il devient le compagnon de la chanteuse américaine Linda Sharrock, installée en Autriche[3]. Ils participent à de nombreux groupes, dont Air Mail[1] ou les Pat Brothers (avec Wolfgang Mitterer aux synthétiseurs et Wolfgang Reisinger à la batterie)[3].
En 1985, il entame une longue collaboration avec la pianiste et compositrice Carla Bley[1].
En 1987, Puschnig s'intéresse à la musique extrême-orientale, et collabore avec Samul Nori, un ensemble de percussionnistes sud-coréens. Il forme le groupe Red Sun et enregistre plusieurs albums avec des musiciens traditionnels[3].
Son premier album en leader Pieces Of The Dream paraît en 1988. Il quitte alors le Vienna Art Orchestra pour se lancer dans une carrière prolifique[1]. Sous le nom de Gemini, il collabore avec Jamaaladeen Tacuma, ancien bassiste d'Ornette Coleman dans un duo jazz-funk[1].
Avec Sharrock et le pianiste Uli Scherer, il crée le trio AM4 (A Monastic Quartet)[3].
En 1991 sort l'album Alpine Aspects, sur lequel se rencontrent la fanfare d'Amstettner et Jamaaladeen Tacuma[2]. La même année, il fonde le quatuor de saxophones Saxofour avec Florian Bramböck, Klaus Dickbauer et Christian Maurer[2].
En 2008 paraît Homage To O.C., un hommage à Ornette Coleman enregistré avec son ensemble Alpine Aspects[1].
1988 : Two Songs For Another Lovely War (Ex Zed Records), Wolfgang Puschnig/Christian Radovan/Wolfgang Reisinger/Uli Scherer/Heiri Kaenzig/Harry Sokal/Mathias Rüegg
1998 : Holy Aureols Esoteric (Esovision), Wolfgang Puschnig/Stefan Benkö
1998 : Spaces (EmArcy), Wolfgang Puschnig/Mark Feldman
1998 : hot ROOM (Extraplatte), Lechner/Puschnig/Tang/Youssef
