Fin 1941. Après avoir quitté la formation de Cab Calloway avec qui il s’est disputé, le trompettiste Dizzy Gillespie rejoint l’orchestre de Benny Carter. En 1942, l’ensemble est sollicité pour participer à un « soundie »Très en vogue au début des années 1940, les soundies sont de courts films que l’on pouvait visionner en insérant une pièce dans une machine, à la manière d’un jukebox. : A Case of the Blues. D’après Gillespiepropos extrait de To be or not to bop de Dizzy Gillespie et Al Fraser, Éditions Presses de la Renaissance, 1981 c’est lors d’une pause pendant les séances de répétitions pour ce film qu’il aurait composé Night in Tunisia, d’abord intitulé Interlude : je me suis mis au piano et j’ai plaqué quelques accords de treizième et leur résolution, et peu à peu, en égrenant les notes, je me suis aperçu qu’elles formaient presque une mélodie, à laquelle il ne manquait plus qu’un pont et un support rythmique. Dès que je suis sorti de cette séance, j’ai vite noté mon idée. Un rythme syncopéune ligne de basse qui ne marquait plus chacun des quatre temps ("boom-boom-boom-boom") mais devenait syncopée ("boom-be, boom-be")
(propos de Gillespie extrait de To be or not to bop de Dizzy Gillespie et Al Fraser, Éditions Presses de la Renaissance, 1981), une mélodie complexe et anguleuse, autant de caractéristiques qui font l’originalité du style de Gillespie et qui entraîneront le jazz sur la pente du be-bop. L’anecdote racontée par Art Blakey, selon laquelle Gillespie aurait composé le titre en improvisant un bureau sur le couvercle d’une poubelle, est plaisante mais sans doute fantaisiste et réfutée par le principal intéressé.

Quelques mois plus tard, Gillespie intègre l’ensemble de Earl Hines, à qui il propose son arrangement de Night in Tunisia. Hines revendique la paternité de ce second titre qu’il aurait choisi en raison des événements ayant lieu en Afrique du Nord à cette époque, mais Gillespie réfute également cette affirmation. Quoi qu’il en soit, c’est dans l’orchestre de Hines que le trompettiste rencontre le saxophoniste Charlie Parker, qui deviendra un ami très proche et un partenaire de jazz privilégié, ainsi que la chanteuse Sarah Vaughan et Billy Eckstine qu’il suivra en 1944 pour former l’un des premiers ensembles be-bop.

Le premier enregistrement connu du titre est celui réalisé par Sarah Vaughan le 31 décembre 1944, sous le nom Interlude, pour le label Continental. Leonard Feather, critique de jazz et promoteur, se souvientpropos extrait de To be or not to bop de Dizzy Gillespie et Al Fraser, Éditions Presses de la Renaissance, 1981 de cette séance d’enregistrement : J’ai fini par décrocher une séance avec une compagnie, Continental Records, et l’enregistrement eut lieu le jour de la Saint-Sylvestre en 1944, avec Dizzy, et Georgie Auld au ténor, une sorte de all-star sans pianiste car je ne disposais que d’un très petit budget. J’ai décidé de me mettre moi-même au piano, bien obligé ! Il y avait quatre morceaux prévus, dont Night in Tunisia ; mais pour ce dernier, assez complexe, mon oreille n’était pas à la hauteur et je n’étais pas non plus un bon lecteur. Bref, je n’arrivais pas à m’en sortir et c’est Dizzy qui a dû me remplacer pour une partie de ce morceau dans lequel il jouait aussi de la trompette. Quelques semaines plus tard, le 26 janvier 1945, Dizzy Gillespie enregistre à nouveau le titre, cette fois sous le nom de Night in Tunisia : avec l’orchestre de Boyd Raeburn, il gagne en énergie grâce à un tempo plus rapide et plus de cuivres dans l’arrangement. Joué et enregistré à plusieurs reprises, par Gillespie et bien d’autres, le titre devient rapidement très populaire. Il est souvent intitulé A Night in Tunisia, contre l’avis de Gillespie cependant qui préfère le titre sans article.

Crédité comme coauteur, Frank Paparelli n’aurait cependant rien à voir avec la composition du thème : Frank Paparelli a transcrit mes solos pour les faire éditer, et c’est en quelque sorte pour l’en remercier que j’ai ajouté son nom comme coauteur, mais il n’a pas participé à l’élaboration du thème, déclarepropos extrait de To be or not to bop de Dizzy Gillespie et Al Fraser, Éditions Presses de la Renaissance, 1981 Dizzy Gillespie.

Quarante ans après la composition de Night in Tunisia, Jon Hendricks, l’auteur des paroles originelles, participe à une reprise du standard par Bobby McFerrin et The Manhattan Transfer. Intitulé Another Night in Tunisia, le titre remporte le Grammy Award de la meilleure performance vocale jazz.

Écouter le thème de Night in Tunisia, de forme AABA :