All’epoca della sua uscita, la Count Basie band ottenne un grande successo con l'album April in Paris, in un momento in cui la band ne aveva davvero bisogno. Con la crescente popolarità del Bebop e cool jazz, (e del rock & roll, poco dopo), sostenere una big band era diventato estremamente difficile. Basie stesso aveva dovuto rinunciarvi per un po 'di tempo nel 1950, smantellando l'orchestra e suonando solo con un piccolo gruppo. Tuttavia, un paio di album ben particolarmente riusciti nella metà degli anni Cinquanta gli diedero la possibilità di andare avanti con la sua amata orchestra. Uno di questi LP è il celebre Atomic Mr. Basie, con le canzoni e gli arrangiamenti di Neal Hefti. L'altro, registrato un anno prima, è appunto April in Paris, che contiene anche un brano composto e arrangiato da Hefti. Tuttavia, l'album è conosciuto soprattutto per il brano omonimo - una straordinaria rilettura del noto brano firmata dall’organista Wild Bill Davis.