Heinistä voidaan pitää ensi sijassa orkesterisäveltäjänä. Hänen tuotantonsa keskeisiä teoksia ovat viisi sinfoniaa, neljä pianokonserttoa, konsertto alttosaksofonille ja orkesterille, viulukonsertto, sellokonsertto, ''Adagio'' ("konsertto orkesterille variaatioiden muodossa"), ''Poesia squillante ed incandescente'', jousikvintetto, ''...tyttöjen kävely ruusulehdossa...'' jousiorkesterille sekä oopperat ''Silkkirumpu'' ja ''Veitsi''.
Heininen on säveltänyt lukuisia kamarimusiikki- ja sooloteoksia erilaisille kokoonpanoille, viime vuosikymmenen aikana mm.muun muassa pianolle ja uruille. Hänen huilukonserttonsa<ref>{{Verkkoviite | Osoite =http://yle.fi/uutiset/kulttuuri/2010/09/paavo_heinisen_huilukonsertto_kantaesitetaan_lappeenrannassa_2019121.html| Nimeke =Paavo Heinisen huilukonsertto kantaesitetään Lappeenrannassa. | Julkaisija =Yle.fi | Viitattu = 29.9.2010}}</ref> ''Autrefois'' kantaesitettiin syksyllä [[2010]] [[Lappeenrannan kaupunginorkesteri]]n konsertissa. RSO kantaesitti Heinisen ''Eläinten Te Deum'' -oratorion kaksi osaa konsertissaan tammikuussa 2013 (Kaukametsä ja Musta kehtolaulu).
