Первым инструментом Пола была гитара, но затем, находясь под влиянием Коулмена Хокинса, он перешёл на саксофон и уже в начале 1940-х гг. играл на теноре в бэнде Сабби Льюиса. После армии (1942-1945) он нередко работал в оркестрах Каунта Бэйси (1946-1947) и Диззи Гиллеспи (1949-1950), а в сентябре 1950 г. его пригласил к себе Эллингтон, и Пол остался с ним более чем на два десятилетия, до конца своей жизни.
Скромный, добродушный и весёлый человек, он заполнил тот пробел, который остался в рядах саксофонистов Эллингтона после ухода Бена Вебстера.
Гонзалвес был способен бесконечно нанизывать квадрат за квадратом в своих быстрых соло, но к творческим высотам его поднимала тёплая, рапсодическая трактовка баллад. Обладая богатым тоном звучания, он был настоящим мастером баллад — и здесь вспоминается наш саксофонист Игорь Лундстрем, брат Олега Лундстрема.
В середине 1950-х гг. в карьере Эллингтона наблюдался спад, и он иногда говорил: «Я родился второй раз в 1956 г. на джаз-фестивале в Ньюпорте». Его бэнд появился там на сцене очень поздно вечером, когда публика уже собралась уходить, и Дюк объявил пьесу «Diminuendo & Crescendo In Blue». Через пару минут люди вернулись обратно, по толпе прошёл ток. У микрофона на теноре солировал Пол Гонзалвес, не останавливаясь ни на миг, с неослабевающим напором. Вскоре всё слилось в один динамический перкуссивный корус, вокруг кричали «Ещё, ещё!», сотни пар начали танцевать, а организаторы фестиваля испугались, что всё пойдёт вразнос и толпа станет неуправляемой. Никто не знает, как наступают такие эмоциональные моменты. А Гонзалвес продолжал дуть, сыграв (по самому скромному подсчёту) двадцать семь квадратов, хотя, по мнению слушателей, их было сто двадцать семь. Это был поворотный пункт в карьере Эллингтона, а Гонзалвес стал героем Ньюпорта. Он вспоминал, как однажды на другом концерте владелец зала выразил ему свои сомнения: «Я не верю, что вы могли так долго играть в Ньюпорте!» Гонзалвес сделал ему одолжение и исполнил шестьдесят шесть квадратов.
Его талант не раз раскрывался в таких сольных шедеврах, как «Solitude» (1950), «Circle Of Fourths» (1957), «Happy Reunion» (1958), «Mount Harissa» (1966) из знаменитой «Дальневосточной сюиты» Дюка, а помимо записей с Эллингтоном он также сделал ряд альбомов и под своим собственным именем — «Getting Together», «Cleopatra Feelin Jazzy», «Tell It The Way It Is», «Humming Bird», «Just A-Sittin & A-Rockin».
