В. Мулерман родился в 1939 году в Одессе. Петь начал еще в детстве, когда учился в школе. В восемь лет начал курить, что было делом не случайным: в 4,5 года он попал на передовую, и там, в землянке, кто-то из солдат для хохмы угостил его самокруткой.
Музыкальное образование Мулерман получил в Харькове, там же окончил консерваторию. Подавал большие надежды как оперный певец. Однако затем был призван в ряды вооруженных сил и служил в ансамбле Киевского военного округа. Вернувшись на гражданку в начале 60-х, хотел было возобновить карьеру оперного певца, но семейные обстоятельства помешали этому: в то время у него сильно болел отец и пришлось думать о хлебе насущном. Поэтому певец отправился на эстрадную сцену. В 1965 году он сначала работал в Дагестане с ансамблем Кажлаева, затем в оркестре Анатолия Кролла в Туле. Во время одного из выступлений его приметил Юрий Саульский и пригласил в Москву.
Приехав в столицу, Мулерман одно время не имел собственной крыши над головой и ночевал на Курском вокзале. Местный милиционер за рубль охранял от посягательств других ночлежников его лавочку. А вскоре директор Театра эстрады на деньги театра (естественно, в долг) помог Вадиму снять номер в гостинице «Балчуг» на полгода.
В 1966 году на Всесоюзном конкурсе эстрадных исполнителей Мулерман стал лауреатом. Так как конкурс транслировался по телевидению, его увидела вся страна. К молодому певцу потянулись маститые композиторы с предложениями о сотрудничестве.
Первым всесоюзным шлягером Мулермана стала песня «Лада» В. Шаинского — М. Пляцковского. Затем появились: «Хромой король», «Трус не играет в хоккей», «Гуцулочка» и др. К певцу пришла оглушительная слава. Когда он ехал на гастроли, к поезду прицепляли еще два вагона с девочками-поклонницами. Во время его концертов в Театре эстрады в Москве вся окрестность оцеплялась конной милицией. Под прицелом досужих языков оказалась личная жизнь артиста. Буквально на всех московских кухнях в те годы только и было разговоров о том, как Мулерман увел у И. Кобзона жену — красавицу певицу Веронику Круглову.
Стоит отметить, что Мулерман оказался одним из первых советских певцов, кто стал расхаживать по сцене с микрофоном. Это произошло на очередном Всесоюзном конкурсе артистов эстрады. Жюри конкурса было очень недовольно этой выходкой артиста, назвало его «хулиганом».