1981–1982 war Fleissner Assistent des Künstlerpaars Mario und Marissa Merz. 1986–1987 studierte er an der Hochschule für angewandte Kunst in Wien, 1987–1993 folgte ein Studium an der Akademie der bildenden Künste in Wien. Der ehemalige Punk-Musiker versteht sich als Maler, Zeichner, Bildhauer und Objektkünstler.
In seinen bildhauerischen Arbeiten beschäftigt er sich mit der Wegwerfgesellschaft und deren überflüssig gewordenen Gegenständen. In seinen Werken greift er auf den Materialabfall der Umwelt zurück, macht aus etwas bereits Vorhandenem ein neues Objekt und eröffnet somit neue Perspektiven und Interpretationsspielräume. Restmaterialien der Verbrauchskultur werden durch eine neuerliche Bearbeitung zusammengefügt. Seine bildhauerische Arbeit setzt immer wieder neu an und sein Schaffen ist sehr vielseitig. In seinen Assemblagen, Plastiken und Installationen versucht der Künstler einen Brückenschlag zwischen Alt und Neu.
Fleissners Objekte wurden 1991 in der Wiener Secession, 1992 im Rahmen des „steirischen herbstes“ und 1994 im Museum of Modern Art in New York ausgestellt. 2001 wurden seine Werke in der Neuen Galerie Graz sowie 2002 im Stadtmuseum Graz gezeigt.