Formé à la fois à la musique classique et au jazz, il débute à 14 ans dans les bals comme accordéoniste. Il accompagne la chanteuse Renée Lebas qui lui présente Georges Brassens et surtout Boris Vian en [3]. L'auteur pataphysicien et grand amateur de jazz, qui vient d'essuyer un échec avec L'Arrache-cœur, cherche un nouveau mode d'expression et décide de mettre certains de ses textes en musique.
Au cours de leur année de collaboration, Vian et Walter produiront ainsi plus d'une quinzaine de chansons, parmi les plus connues de Vian, dont la plupart sont enregistrées en avril 1955 sous les titres Chansons possibles et Chansons impossibles, avec Walter à la tête de son ensemble. Ils donnent également une série de récitals aux Trois Baudets, dirigé par le producteur Jacques Canetti. Directeur artistique chez Philips, ce dernier lui propose de devenir l'arrangeur des artistes dont il s'occupe. Pris par cette nouvelle occupation et désireux de sortir de l'ombre de Vian, Walter entame une collaboration avec notamment Claude Nougaro, Serge Reggiani, Jacques Higelin, Mouloudji, Brigitte Fontaine, tandis qu'Alain Goraguer le remplace auprès de Vian.