Paolo Tombolesi ha conseguito i diplomi di pianoforte e di jazz, e il Diploma Accademico di Secondo Livello in Jazz presso il Conservatorio di Frosinone studiando sotto la guida, tra gli altri, di Gerardo Iacoucci, Enrico Pieranunzi e Walter Fischetti. Inoltre ha seguito corsi e seminari di perfezionamento con Gary Burton, Sal Nistico, Bruno Tommaso, Franco D'Andrea, Mike Melillo, Miroslav Vitous, Alfredo Rodriguez, Harold Danko, Barry Harris e Kenny Barron. Nel 1991 è stato invitato come studente ospite presso la Manhattan School of Music di New York.
La sua attività concertistica in ambito jazzistico inizia accompagnando il coro "The New Spiritual Singers", diretto da Gerardo Iacoucci (1981/82) sotto la cui direzione ha anche lavorato dal 1983 al 1992 nella "Modern Big Band", con cui ha avuto modo di accompagnare tra gli altri Dusko Gojkovich, Gianni Basso, Jens Søndergaard, Steve Grossman e John Mosca. Tra il 1983 e il 1984 collabora con il "Blue Quintet" diretto da Alfredo Santoloci, tra il 1987 e il 1989 con il "Kammerton Vocal Ensemble" diretto da Fabrizio Cardosa e negli anni 1989/90 con il gruppo di salsa e latin jazz "Raiz" diretto da Jesus Zeballos. Nel corso degli anni '80 inoltre si è esibito più volte nell'orchestra di "Segni Jazz", diretta da Bruno Tommaso, in concerti con Gianluigi Trovesi, Danilo Terenzi, Ettore Fioravanti, Enzo Pietropaoli, Maurizio Giammarco e Umberto Fiorentino. Nei primi anni '90 fa parte del quartetto di Daniela Velli ed è tra gli animatori dell'ottetto "Sax Energie" (con Rosario Giuliani, Mauro Verrone, Andrea Polinelli, Massimo Bettazzi, Andrea Pace, Enrico Ghelardi, Giampiero Merluzzi, Giancarlo Guidoni, Stefano Pacioni ed altri). Nel 1991 forma, insieme a Mauro Verrone, Stefano Cantarano e Maurizio Rizzuto (a cui poi è succeduto Paolo Mappa), il quartetto "Percorsi", un progetto portato avanti fino al 1995, avvalendosi in alcuni concerti della collaborazione di Maurizio Giammarco.
Dal 1994 al 2003 ha suonato con la cantante Marilena Paradisi in verie formazioni, collaborazione culminata nella registrazione di un CD in quartetto ed una serie di concerti con Piero Leveratto e Eliot Zigmund.
Nel maggio 2000 è stato in Africa con il GASP QUINTEM diretto da Andrea Pace, dove ha suonato in Zimbabwe (Harare International Festival of Arts), Kenya ed Etiopia. Tra i molti altri musicisti che Paolo Tombolesi ha affiancato come "freelance" vi sono Massimo Urbani, Bruno Tommaso, Maurizio Giammarco, Mark Murphy, Alvin Batiste, Scott Reeves, Terrell Porter, Jay Rodriguez e Charles Davis.
Attualmente svolge la propria attività concertistica prevalentemente con il proprio trio, con Gianluca Renzi al contrabbasso e Alessandro Marzi alla batteria. Con questo trio ha registrato nel mese di ottobre 2003 il CD intitolato "Unawares", e alcune composizioni originali presenti nel disco sono state incluse nell' ITALIAN JAZZ REAL BOOK.
Nel 1992 ha fatto parte del Comitato Regionale lazio e nel 1993 del Consiglio Direttivo Nazionale dell' AMJ (Associazione Musicisti di Jazz).
La sua attività didattica si è svolta principalmente presso: C.I.A.C. (Roma) 1986/1992, Centro Musicale Latina 1988/89, Scuola Comunale di Musica di Orvieto 1989/1998, "Jazz University" di Terni 1990/1992, Scuola Comunale di Musica di Ferentino 1990/92, St. Louis Music Accademy (Roma) 1991/92, Scuola di Musica Neuma (Roma) , di cui è anche uno dei fondatori ed animatori, dal 1993 a tutt'oggi.
E' assistente al coordinamento del Dipartimento di Jazz presso il Conservatorio di Musica "Licinio Refice" di Frosinone.

Ha registrato a proprio nome:

"UNAWARES" - Paolo Tombolesi Trio with Gianluca Renzi and Alessandro                   Marzi (Philology W 712 - registrato nel 2003, pubblicato nel 2004)

Tra le sue collaborazioni discografiche vanno citati i dischi:

"Modern Big Band" - direttore: Gerardo Iacoucci (Flippermusic 1987)

"Great News From Italy" - Gerardo Iacoucci Modern Big Band, featuring Paolo Fresu, Enrico Pieranunzi, Sandro Satta, Pietro Tonolo, Gianluigi Trovesi (yvp music 1992)

"For you: a tribute to Bruce Springsteen" - AA.VV. (Sony 1994)

"Primi Piani live" - a cura di Luigi Cinque. 50 pianisti diretti da Bruno Tommaso a Roma a Piazza del Popolo, nella notte di Capodanno 1994/95. Pianisti solisti: Marco Fumo, Antonello Salis, Richard Trythall, Marco Tiso, Danilo Rea, Riccardo Fassi, Cinzia Gizzi, Paolo Tombolesi, Andrea Alberti, Stefano Sabatini e Fabrizio Pieroni. (Multirifrazione Records 1995)

"Se amando troppo" - Dacia Maraini/Giuseppe Moretti (Rizzoli 1999)

"Mr. Max" - Francesco Di Giovanni (Il Pozzo dei Desideri 2001)

"Beatin' Beats" - Toni Germani Quartet (DISCHI DELLA QUERCIA 128049-2 - registrato nel 1999, pubblicato nel 2002)

"I'll never be the same" - Marilena Paradisi - con Marilena Paradisi, voce - Piero Leveratto, contrabbasso - Eliot Zigmund, batteria (Philology W 223.2 - 2002)

"Lost Love" - Enrico Ghelardi Boptet (domani musica DMCD 0205) - registrato nel 2001, pubblicato nel 2002

"Il manto di Arlecchino" - numinoso ensemble - 2003

“A Child Is Born” - Marcello Rosa - con Andy Gravish, Max Ionata, Gianluca Renzi,  ecc. - (Philology W 290 - 2007)

"Jass & Jazz & More" - Marcello Rosa - con Andy Gravish, Max Ionata, Gianluca Renzi,  Alessandro Marzi, ecc. - (Pentaflowers CDPIA 056 - 2008)