Das Hören von Musik verbunden mit der Sympathie für Musiker, spiegelt sich in der kolossalen Schallplatten und CD-Sammlung, mit der Stein sich umgab. Verschiedene Genres der sogenannten U-Musik waren ständige Begleiter seiner Arbeit und stimulierten ihren Fortgang. Dies findet direkt seinen Ausdruck in den Aufzeichnungen über gehörte Musikstücke, die mit Titel und Laufzeit akribisch in den „Skizzbüchern“ vermerkt werden.

Stein selber spielte kein Instrument und das punktuelle Zuhören eines direkten Instrumentenspiels konnte ihn in seiner Andersartigkeit gegenüber dem Tonträger regelrecht überraschen.

Musik transponiert diverse Formen der Grenzerfahrungen. So verbindet Paul Stein eine Geschichte zu Maradonas Drogenkonsum mit dem grafisch sichtbar gemachten Klangkörper eines Tenorsaxophons. Die sichtbar gemachte Improvisation des Free Jazz umspielt auf diese Weise die Erzählung um das drogenunterstützte Genie des Fußballgottes.

Mehr auf das Systematische des Komponierens hebt die minimalistische Notation ab, die das Gerüst der Notenfolgen durch einzelne Zeichen für Pause und Betonung ersetzt. Solche Notationsbilder zeichnen sich in eine Verbindungslinie zu den grafischen Notationen eines John Cage. Parodistische Untertöne sind unverkennbar.