"L’Etonnant Serge Gainsbourg", son troisième album sort au printemps 1961. ("En relisant ta lettre", "Viva Villa"...).
Il n’a pas encore trouvé son style, n’a pas fidélisé un public contrairement à Brel ou Brassens, il est de plus en plus malheureux de chanter dans un cabaret où les gens l’écoutent distraitement tout en buvant et mangeant. D’autant qu’en plus de chanter il lit des textes de Bossuet sur scène.

Son quatrième album, N°4, sort au printemps 1962 et se vend si mal, qu’il songe sérieusement à abandonner le métier. Pourtant il vient de signer une des plus belles chansons de son répertoire : "La javanaise" inspirée par Juliette Greco et composée pour elle après avoir passé une soirée chez elle à écouter de la musique classique, jusqu’aux aurores, et à boire de grands vins.
Le lendemain elle avait reçu un magnifique bouquet d’orchidées accompagné d’un petit mot lui annonçant qu’il venait de lui écrire une chanson inspirée par cette soirée. "Il est arrivé chez moi, me l’a joué au piano et je suis tombée … C’était magnifique, qui ne serait pas bouleversé par ça ?
C’était tellement proche de moi, c’était nous aussi. Et je sais très bien pourquoi il l’a écrite. Mais c’est mon affaire, c’est secret !"
(Juliette Greco)

En novembre 62, Brigitte Bardot se lance dans la chanson et lui demande d’écrire un titre pour son premier E.P., puis un autre pour son 1er album, il lui offrira : "Appareil à sous", "Je me donne à qui me plait", un titre écrit sur mesure !
Plus tard il tentera de la rappeler, sans succès, mais elle avait changé de ligne, et du coup elle lui inspira ces quelque vers, chanté par Isabelle Aubret au grand prix de l’Eurovision :

Il n’y a plus d’abonnés au numéro que vous avez demandé
Vous qui m’avez laissé tomber
A quoi vous sert de me relever
Dans l’annuaire adieu adieu ne vous déplaise
Les réclamations c’est le treize