Quan el 1955 es van aturar al Café Bohemia a Greenwich Village on tocava Oscar Pettiford va ser el punt d’ionflexió de la seva vida. Tots dos es van presentar a punt per tocar. Es va demanar a Cannonball que s’assegués perquè el saxofonista habitual estava fora i va aclaparar els músics. Aleshores Nat es va posar a l’escenari i tothom va quedar impressionat. Les ofertes de feina van començar a arribar i Nat va gravar per primera vegada.

El so del grup es va fer conegut com a soul jazz, començant el gènere, tot alternant-ho amb hard bop.

La seva cançó més reeixida va ser  Work Song. Adderley la va qualificar de la seva “cançó de la Seguretat Social” a causa del flux constant d’ingressos durant els anys des dels pagaments de regalies quan altres van gravar la cançó. Ara es considera un estàndard de jazz.

Amb el seu quintet van establir la majoria d’edat del soul jazz. Aquest estil recupera un tipus de jazz més senzill que tenia influència directa del blues i de la música de l’església.

I com no, ara escoltarem Work Song.

.