Paul Dessau wurde am 19. Dezember 1894 in Hamburg geboren. Sein Großvater war Kantor an einer Hamburger Synagoge. Paul bekam seit dem 6. Lebensjahr Geigenstunden und besuchte von 1910 bis 1912 das Klindworth-Scharwenke-Konservatorium, entschied sich jedoch für die Dirigentenlaufbahn. 1912 begann er als Korrepetitor am Stadttheater in Hamburg; ab 1919 war er, neben anderen Theaterstationen, unter Otto Klemperer an der Kölner Oper engagiert und wechselte später an die Städtische Oper Berlin zu Bruno Walter.

Mittlerweile hatte er sich als Komponist einen ersten Namen gemacht. Bald wurde er auch von dem neuen Medium Film angezogen und begann eine außergewöhnliche Karriere als musikalischer Leiter an verschiedenen Filmtheatern. In dieser Zeit arbeitete er intensiv daran, neue musikalische Elemente und einen neuen Sound in seinen Filmmusiken zu entwickeln. Seine erste experimentelle Tonfilm-Musik wurde unter dem Titel Episode 1929 beim Kammermusikfest Baden-Baden aufgeführt; zwei Jahre zuvor hatte er dort auch Bertolt Brecht kennen gelernt. Neben seiner Arbeit als Filmkomponist schuf er auch Konzertwerke und Stücke für Arbeiter-Kinderchöre.

1933 emigrierte er nach Paris, wo er seinen Lebensunterhalt unter anderem mit Kompositionen für andere gleichfalls emigrierte deutsche Filmregisseure verdiente. Eine Begegnung mit René Leibowitz 1936 brachte ihn in Berührung mit der Zwölftonmusik. Nach Ausbruch des Spanischen Bürgerkriegs komponierte er unter Pseudonym politische Marschlieder, wie z.B. Thälmannkolonne auf einen Text seiner ersten Frau Gudrun Kabisch. In dieser Periode seines Schaffens entstanden auf der Suche nach seinen religiösen Wurzeln auch Kompositionen über jüdische Themen. 1938 schrieb er die Schauspielmusik zu Brechts Furcht und Elend des Dritten Reiches (aufgeführt unter dem Titel 99%), das in der Regie von Slatan Dudow aufgeführt wurde.

Ein Jahr später emigrierte er nach New York, wo er 1943 bei einem Anti-Nazi-Konzert, bei dem sein Kampflied der schwarzen Strohhüte von 1936 aufgeführt wurde, Brecht wieder traf. 1943 zog Paul Dessau nach Hollywood, wo er, neben engen Kontakten zu Arnold Schönberg, vornehmlich als Komponist und Arrangeur für Filmstudios arbeitete. Mit der wieder aufgenommenen Zusammenarbeit mit Brecht begann in dieser Zeit ein neuer Abschnitt in seinem Schaffen; Dessau wandte sich verstärkt politischen Themen zu und trat 1946 der US-KP bei.

1948 kehrte er nach Deutschland zurück. Seine Oper Das Verhör des Lukullus nach einem Text von Brecht wurde 1951 nach der Uraufführung in Berlin im Kontext der Formalismus-Debatte und der Diskussion über sozialistischen Realismus in der Kunst der DDR kritisiert. Nach intensiven Diskussionen mit Brecht, der Veränderung einiger Szenen und vor allem des Schlusses und einer Änderung des Titels in Die Verurteilung des Lukullus wurde die neue Fassung im Oktober des gleichen Jahres ebenfalls in Berlin uraufgeführt, dann jedoch bis 1960 nicht mehr gespielt.

1952 wurde Dessau Mitglied der Akademie der Künste und widmete sich nun mit großer Kraft der musikalischen Erziehung von Schulkindern. Das nächste bedeutende Theaterprojekt, Der kaukasische Kreidekreis, begann er 1953, nachdem Brecht sich endgültig auf Dessau als Komponisten festgelegt hatte. Nach der Uraufführung dieses Stückes zog Dessau nach Zeuthen bei Berlin, wo er bis zu seinem Tode lebte.

Der überraschende Tod von Brecht im August 1956 berührte auch Dessaus Schaffen; er musste andere Partner als Textdichter suchen, die mit seinen ästhetischen Sichtweisen übereinstimmten. Dessau wandte sich in dieser Phase erneut und verstärkt der Zwölftonmusik zu und zog damit die Bewunderung junger Komponisten der Avantgarde, wie zum Beispiel von Luigi Nono, auf sich. Zugleich verfolgte er seine Idee der Musikerziehung in einem sozialistischen Staat dadurch, dass er an der Zeuthener Grundschule unterrichtete. Das Ergebnis dieser Arbeit fand seinen Niederschlag in seinem Buch Musikarbeit in der Schule. In dieser Zeit vollendete er zwei weitere Opern, die beide auf Brecht-Stoffen basierten: Puntila wurde 1966 uraufgeführt, Einstein 1974.

Paul Dessau starb in Königs-Wusterhausen bei Berlin am 28. Juni 1979.