В 1935 г. закончил актерский курс Производственно-театральных мастерских при театре МОСПС (создан в 1923 г., в 1930 г. переименован в Театр им. МОСПС, в 1938 г. стал основой Театра им. Моссовета) и был принят в труппу театра. В 1938 г. Зельдин переходит в Театр транспорта (ныне Театр им. Н.В. Гоголя). Здесь актер сыграл в спектаклях, поставленных по классикам мировой литературы: «Без вины виноватые» А. Островского (массовка), «Комедия ошибок» У. Шекспира (Антифон Сиракузский), «Коварство и любовь» Шиллера (Фердинанд).

В 1940 году И. Пырьев утвердил Владимира Михайловича на главную роль (пастуха Мусаиба Гатуева) в свой новый фильм «Свинарка и пастух». Это был уже второй фильм Зельдина, а дебютировал он в картине Г. Рошаля «Семья Оппенгейма». «Пырьев перевернул мою творческую биографию, дал мне профессию и славу», — вспоминает В. Зельдин. Уже во время съемок фильма в июне 1941 г. на Домбае Владимира Михайловича и всю съемочную группу настигла новость о начале войны. Через несколько дней после возвращения в Москву ему пришла повестка с направлением в танковое училище, но меньше, чем через месяц вышел приказ министра кинематографии о продолжении съемок и возвращении всех мужчин, занятых в фильме, на «Мосфильм» с выдачей брони. Съемки продолжались до конца 1941 г. По окончании съемок Владимир Михайлович уехал вместе с киностудией «Мосфильм» в эвакуацию в Алма-Ату. Во время войны Зельдин часто ездил на фронт, выступая в концертных бригадах. В сезоне 1942—43 гг. В. Зельдин служил в Русском драматическом театре в Алма-Ате. Здесь он сыграл одну из любимых своих ролей — Теодоро в «Собаке на сене» Лопе де Вега. Из Алма-Аты театр, а вместе с ним и Владимир Михайлович, переехал в Чимкент. В 1943 г. Зельдин вернулся в Москву, где продолжил работу в Театре транспорта.

В январе 1946 г. Владимир Зельдин дебютировал в роли Альдемаро в спектакле Владимира Канцеля «Учитель танцев» по пьесе Лопе де Вега на сцене Театра Красной (ныне Российской) Армии. Дебют оказался феерическим, спектакль более, чем успешным, и за следующие тридцать лет более 1000 раз Зельдин блистал в роли Альдемаро, а Театр Армии стал для него домом и остается им по сей день. После одного из спектаклей к нему в гримёрку заходила поблагодарить Анна Ахматова, и с этим же спектаклем связан единственный режиссерский опыт артиста, когда Владимир Михайлович сам подготовил молодежный состав во главе с Федором Чеханковым и передал спектакль по наследству.

Владимир Зельдин не изменил Театру Армии, сыграв около 50 ролей, в том числе Транио в «Укрощении строптивой», Поручика Ржевского в «Давным-Давно» (постановка А.Д.Попова), барона Мюнхгаузена в «Комической фантазии о жизни и смерти знаменитого барона Карла Фридриха Иеронима фон Мюнхгаузена» Г. Горина, Л. Папагатто в спектакле «Моя профессия — синьор из общества» и др. В настоящее время занят в спектаклях Театра Армии: «Человек из Ламанчи», «Давным-давно», «Загнанная лошадь», «Приглашение в замок».

«Он один из немногих на русской сцене сумел придать легкому жанру (так востребованному в сталинские времена и кровожадной властью, и уставшей от политического людоедства публикой) необходимую легкость…Его голос, обаяние, энергетика, в отличие от всяких там канонов, и впрямь не подвержены коррозии времени. Они на все времена».

Марина Давыдова, «Известия»