Paolo Cataldi nasce a Bari nel 1936 e già in giovanissima età è attratto dai mezzi espressivi quali pennelli, bulini, legni di ogni genere, argilla. A Terlizzi dove viveva spesso presso la nonna materna, incomincia a modellare e ad incidere. A 16 anni con il coetaneo Vito Magaletti tornitore, costruisce un torchio calcografico per stampare xilografìe ed acquaforti. Frequenta L’Istituto Statale d’Arte di Bari, e, da studente, entra a far parte dello studio del pittore Antonio Rega dove ha modo di conoscere artisti e critici quali Pietro De Giosa, Pietro Marino, Lello Spinelli, Inigo De Maria, Franco Sossi, Michele Campione, Gustavo Del Gado interessati alla sua espressione artistica.

Stimato e considerato dai propri maestri spesso lavora con loro, in particolare, con Francesco Spizzico, Lorenzo Perrelli, Roberto De Robertis, Leopoldo Romandini per la realizzazione di decorazioni, affreschi, e graffiti. Frequenta il bar Sottano, luogo di incontri culturali, politici ed artistici. Tra gli incontri più prestigiosi sono da ricordare l’onorevole Aldo Moro, l’onorevole Renato Dell’Andro, lo scultore ungherese Amerigo Tot ed il senatore Luigi Russo che, in seguito, lo chiamerà ad insegnare presso il nascente Istituto Statale D’Arte di Monopoli. Negli anni sessanta sempre nello studio di Antonio Rega conosce il pittore Cantatore e lo scultore Cesare Marino con il quale instaura un rapporto di amicizia e lavoro.

Inizia così un periodo dì intensa attività artistica con mostre in varie località e a Bari nella Galleria Piccinni. In seguito, in Via Garruba insieme a Tony Prayer e Ugo Martiradonna, apre uno studio che, per tre anni, diventa punto d’incontro degli artisti baresi (Umberto Baldassarre, Nicola Lafortezza, Nicola Sportelli, Vito Ceglie, Guido Prayer, Mario Sportelli, Gianni Angiolillo ecc.).
In questi anni dal maestro De Robertis viene presentato all’editore Macinagrossa ed al professor Prandi docente di storia dell’arte presso l’Università di Bari. Anche con loro si instaura un rapporto, di lavoro. Il Dottor Macinagrossa in occasione di un’asta di beneficenza per l’alluvione di Firenze, al teatro Petruzzelli propone delle sue xilografie. Come docente presso l’Istituto D’Arte di Monopoii rivede il pittore Enrico Accatino nominato Direttore già incontrato a Roma al Palazzo delle Esposizioni in una mostra internazionale su tema sacro alla quale entrambi avevano partecipato. Tra i due nasce una grande collaborazione. Insieme organizzano mostre didattiche con esposizione all’estero.

Intanto realizza una mole ingente di lavori di pittura, scultura e incisioni confrontandosi con svariati materiali: argilla, legno, ferro, bronzo, gesso, marmo e tutto quanto riguarda la tecnica della scultura. In pittura esegue oli, acquerelli, disegni, affreschi, graffiti, decorazioni su vetro, illustrazioni su testi di poesie e racconti. Di notevole pregio i bassorilievi delle porte legno decorato realizzate per civili abitazioni.
Di grande impegno sono le tre porte in gesso patinato a misura reale per la cattedrale di Monopoli esposte nella Biblioteca Comunale e la porta in Bronzo della Chiesa Madre di Picerno di recente creazione. Interessanti sono inoltre, gli intarsi in marmi policromi, di grandi dimensioni per cappelle funerarie nel cimitero di Monopoli. Numerose altre opere di ogni genere figurano in prestigiose collezioni pubbliche e private. Nel corso della sua lunga carriera artistica ha partecipato ad un grande numero di mostre sia regionali che nazionali ed internazionali conseguendo premi e riconoscimenti.

Non più tanto giovane ma neanche anziano, continua tuttora la sua frenetica attività artistica, nelle varie forme a luì congeniali presso il proprio laboratorio d’arte al n. 41 di Via Bixio a Monopoli e presso la casa di campagna.