Alain Delon et Jean Gabin éprouvaient l'un pour l'autre une très grande affection. Au point que les deux hommes se redonneront la réplique dans Le Clan des Siciliens (1969) du même Henri Verneuil et Deux hommes dans la ville (1973) de José Giovanni. Fidèle à la famille Gabin, Alain Delon sera présent lorsque les cendres du monstre sacré seront dispersés en mer le 19 novembre 1976.
Durant le tournage, les tensions entre Alain Delon et Henri Verneuil furent à ce point fréquentes que l'assistant-réalisateur Claude Pinoteau devait leur servir parfois d'intermédiaire.
Mélodie en sous-sol compte à son générique deux brillants assistants-réalisateurs, Claude Pinoteau et Costa-Gavras, qui feront respectivement leurs preuves derrière la caméra avec La Gifle (1974) et Z (1967).
A l'origine, le choix des producteurs pour le rôle de Francis Verlot s'était porté sur Jean-Louis Trintignant.
Mélodie en sous-sol est l'adaptation du roman The Big Grab écrit par John Trinian. C'est Michel Audiard qui eut la brillante idée de cette transposition cinématographique.
Durant le tournage, Jean Gabin et Michel Audiard se brouillèrent au point que le comédien refusa de jouer dans Les Tontons flingueurs (1963). Le vétéran trouvait en effet que son rôle n'avait pas assez d'importance et que Maurice Biraud, ami du dialoguiste, était trop mis en avant dans le film. Les ennuis gastriques du "Vieux" n'allaient pas pour arranger les choses.
A l'origine, Henri Verneuil et Michel Audiard avaient en tête de faire tourner Jean Gabin dans un film d'aventure sur les colonies en Orient ou en Afrique, et puis tout a bifurqué vers un film de braquage dont l'action était supposée se dérouler à Deauville. Il faut dire que l'acteur n'acceptait plus trop tôt de tourner hors des frontières françaises. Finalement, changement de décor : c'est au Palm Beach de Cannes qu'eut lieu le casse en question.
Mélodie en sous-sol est le quatrième film que Jean Gabin et Henri Verneuil ont tourné ensemble après Des gens sans importance (1955), Le Président (1961) et Un singe en hiver (1962). Ils se retrouveront en 1969 dans Le Clan des Siciliens qui signera également les retrouvailles des deux hommes avec Alain Delon.
La Metro-Goldwyn-Mayer, qui finançait en partie Mélodie en sous-sol, refusait d'engager Alain Delon, car Jean Gabin leur suffisait comme tête d'affiche. Mais comme l'acteur tenait particulièrement au projet, il renonça à son cachet et proposa de jouer dans le film en échange des droits sur le Japon, l'URSS et l'Argentine. Belle inspiration puisque le film fut un succés international et qu'il lui rapporta de quoi largement compenser son manque à gagner initial.
Acteur internationalement reconnu, Alain Delon voulait améliorer sa côte de popularité auprès du public français, qui lui préférait à l'époque Jean-Paul Belmondo. La réussite d'Un singe en hiver que son "concurrent" avait tourné l'année précédente avec Jean Gabin et Henri Verneuil fut donc l'une des raisons de sa participation à Mélodie en sous-sol.