Born in São José do Rio Preto, where his father was the maestro of a marching band and encouraged his son to train as a tailor, Paulo instead studied in the National Music School and performed with the Brazilian Symphonic Orchestra. He was the first black artist to become first clarinetist in the Municipal Theatre Orchestra. He appeared at Bossa Nova night at Carnegie Hall in 1962 with Sérgio Mendes, the two of them also featuring on Cannonball Adderley's 1962 album, Cannonball's Bossa Nova. He won the Sharp Award for the most popular instrumentalist of the year in 1992.
His CD Paulo Moura e Os Oito Batutas was listed by Barnes & Noble as one of the top 10 recommendations of the year for 1998. From 1997 to 1999, he was on the State Council of Culture in Rio de Janeiro, a Councillor of the Federal Council of Music, and President of the Museum Foundation of Image and Sound. In 2000, Moura became the first Brazilian instrumentalist to win the Latin Grammy. Moura died of lymphoma three days before his 78th birthday. He was married to Halina Grynberg and had two sons, Pedro and Domingos.
- Moto Perpétuo. Chantecler, 1956.
- Sweet Sax. RCA Victor, 1957.
- Escolha e Dance com Paulo Moura. Sinter Discos, 1959.
- Paulo Moura Interpreta Radamés Gnatalli. Continental, 1960.
- Tangos e Boleros. Chantecler, 1962.
- Cannonball's Bossa Nova (1962), with Cannonball Adderley
- Do the Bossa Nova with Herbie Mann, Latin Fever (1962), with Herbie Mann
- Paulo Moura e Quarteto. Equipe, 1968.
- Paulo Moura e Hecteto: Mensagem. Equipe, 1969.
- Paulo Moura e Hecteto: Fibra. Equipe, 1970.
- Pilantocracia. Equipe, 1971.
- Confusão Urbana, Suburbana e Rural. RCA Victor, 1976.
- Concertão. Kuarup, 1981.
- Paulo Moura e Clara Sverner. Odeon, 1983.
- Mistura e Manda. Kuarup, 1984.
- Paulo Moura e Clara Sverner: Vou Vivendo. Kuarup, 1986.
- Paulo Moura e Clara Sverner: Vou Vivendo. Odeon, 1986.
- Gafieira Etc. e Tal. Kuarup, 1986.
- Paulo Moura e Clara Sverner Interpretam Pixinguinha. CBS, 1988.
- Quarteto Negro: Paulo Moura, Jorge Degas, Zezé Mota e Djalma Corrêa. Kuarup, 1988.
- Paulo Moura Interpreta Dorival Caymmi. Chorus, 1991.
- Rio Nocturne. Messidor, 1992.
- Dois Irmãos: Paulo Moura e Raphael Rabello. Milestone Records, 1992.
- Paulo Moura e Wagner Tiso. Tom Brasil, 1996.
- Paulo Moura e Os Batutas. Rob Digital, 1997. Winner of the 2000 Latin Grammy.
- Mood Ingenuo: Paulo Moura and Cliff Korman duo. Jazzheads, 1999.
- Paulo Moura visita Jobim e Gershwin. Pau Brasil, 2000.
- K-Ximblues. Rob Digital, 2002.
- Estação Leopoldina. MecBR, 2003.
- El Negro del blanco. Biscoito Fino, 2004.
- Fruto Maduro with André Sachs, Biscoito Fino 2012
- "MEMÓRIA: Paulo Moura silencia" Zero Hora in Portuguese, 15 July 2010
- "Paulo Moura". Cantaloupe Music Productions Inc. Archived from the original on December 1, 2005. Retrieved 2009-08-06.
- "Músico Paulo Moura morre aos 77". Folha.com. 13 July 2010. Retrieved 13 July 2010.
- "Interview with Seu Jorge" Exclaim! Magazine, August 2010 in Portuguese, 15 July 2010
- Phillips, Tom (22 July 2010). "Brazilian musician brought the bossa nova to the world". The Globe and Mail.