Son mariage avec Elisabeth bat de l'aile, malgré sa timidité persistante et son physique peu avantageux Serge ne pense qu'aux femmes et sait les séduire. Durant l'année 56 le couple se délite, et le divorce à l'amiable sera prononcé le 9 octobre 1957.

En juin 1956 la lente métamorphose en Serge Gainsbourg se concrétise par la déclaration à la SACEM de 4 titres, sous le nom de Julien Gris, qui révèlent - enfin - un talent vraiment original :

Mes petites odalisques
La jambe de bois
Le poinçonneur des Lilas
La cigale et la fourmi

"Qu'on ne me confonde pas avec les autres chanteurs !" dira Serge dès ses débuts…

Il compose pour Michèle Arnaud dont il est très amoureux :

"Elle a été une des chances de ma vie, elle a eu l'intelligence de percevoir en moi un style nouveau."

Mais elle ne retient qu'une chanson : Ronsard 58. Enfin, en décembre 57, mort de trac, poussé par Francis Claude, il monte sur la scène du Milord et chante Le poinçonneur.

"C'était extraordinaire, il avait ce tremblement léger, il avait l'attitude de celui qui est en communication prophétique avec quelque chose, en fait il était en communication avec lui, pas avec le public". (Jacques Lasry).

Le 10 juin 1958, Serge enregistre en studio avec Alain Goraguer et son ensemble :
La jambe de bois, Douze belles dans la peau et Le charleston des déménageurs de piano ;
en juillet, il fait sa deuxième télé, invité par Jacqueline Joubert ; en septembre sort son premier 25 cm sur le verso duquel figure un texte élogieux de Marcel Aymé : […] il chante l'alcool, les filles, l'adultère, les voitures qui vont vite, la pauvreté, les métiers tristes.

Ses chansons inspirées par l'expérience d'une jeunesse que la vie n'a pas favorisée, ont un accent de mélancolie, d'amertume, et souvent la dureté d'un constat. Elles se chantent sur une musique un peu avare où, selon la mode de notre temps, le souci du rythme efface la mélodie. […]
Un autre supporter influent s'exprime pour la 2ème fois dans le Canard enchaîné, dans un article dithyrambique : Boris Vian.

"A la parution de cet article, ma première réaction a été de prendre une gomme et de voir si mon nom pouvait s'effacer... Je l'ai fait parce que je n'en croyais pas mes yeux, j'étais un peu con !" avouera Serge.

A la même époque il se lie avec Françoise-Antoinette Pancrazzi (appelée "Béatrice" par ses amis) qu'il épousera en 1964 et dont il divorcera en 1966. De leur union vont naître Natacha (en 1964) "Totote", "Naufragée, survivante et captive d'un amour brisé" disait-il et Paul (alias Vania) en 1968, conçu pendant une brève période de réconciliation.