Родился 10 февраля 1915 г. в городе Козлове Тамбовской губернии (ныне - Мичуринск Тамбовской области) в семье музыканта Михаила Евгеньевича и учительницы Анны Николаевны Зельдиных. Во время Гражданской войны семья Зельдиных переехала в Тверь, а в 1924 г. – в Москву. После окончания специализированной военной школы хотел поступать в военно-морское училище, однако не был принят туда из-за плохого зрения, после чего начал работать учеником слесаря.
В 1935 г. окончил актерские курсы Театрально-производственного училища при Театре им. Московского областного совета профессиональных союзов (МОСПС, ныне Театр им. Моссовета), затем был включен в актерскую труппу этого театра.
В 1938-1945 гг. работал в Центральном театре транспорта (ныне – Московский драматический театр им. Н.В. Гоголя). На сцене этого театра сыграл в спектаклях "Вторые пути", "Генеральный консул", "Комедия ошибок". Два года во время войны проработал в Русском драматическом театре в Алма-Ате (Казахская ССР).
В 1945 г. Владимир Зельдин пришел в Центральный театр Красной армии (ныне – Центральный академический театр Российской армии), где служил до конца своей жизни. Он был приглашен туда специально на роль Альдемаро в спектакле "Учитель танцев". В этой роли выходил на сцену более тысячи раз, в последний раз сыграл ее в 60 лет.
За годы работы в Театре Российской армии актер создал десятки ролей, среди них Люченцио в "Укрощении строптивой", поручик Ржевский в "Давным-давно", Клайд в "Законе Ликурга", Ринальдо в "Ринальдо идет в бой", барон Мюнхгаузен в "Комической фантазии о жизни, любви и смерти" и др.
Особое место в творчестве актера заняли роли в военно-патриотических спектаклях: капитан-лейтенант Дядичев ("Караван"), командир стрелкового батальона Громов ("Люди, которых я видел"), матрос-артиллерист Ставриди ("Песнь о черноморцах"), командир подводной лодки Петров ("Под одной из крыш"), капитан Бондарь ("Якорная площадь"), Часовников ("Океан") и др.
В 2004 г. специально для Владимира Зельдина в Театре Российской Армии поставлен мюзикл "Человек из Ламанчи". В роли Дон Кихота актер пел, танцевал и играл в драматических сценах. Кроме того, Владимир Зельдин был занят в спектаклях "Танцы с учителем" и "Давным-давно". Также играл в московском театре "Модернъ" в спектакле "Дядюшкин сон".
В фильмографии Владимира Зельдина более 50 ролей. В 1938 г. дебютировал в эпизодической роли в картине Григория Рошаля "Семья Оппенгейма". Роль в фильме "Свинарка и пастух" (1941) принесла актеру всенародное признание. Среди наиболее известных киноработ – "Сказание о земле сибирской" (1947), "Учитель танцев" (1952), "Укрощение строптивой" (1961), "Миссия в Кабуле" (1970), "Дядя Ваня" (1970), "С тобой и без тебя..." (1973), "На край света..." (1975), "31 июня" (1978), "Дуэнья" (1978), "Тайна "Черных дроздов" (1983), "Победа" (1984), "Десять негритят" (1987), "Искушение Б." (1990), "Полицейские и воры" (1997), "Классик" (1998), "Женщин обижать не рекомендуется" (2000), "Андерсен. Жизнь без любви" (2006).
7 октября 2013 г. артист участвовал в московском этапе эстафеты олимпийского огня зимних Олимпийских игр 2014 г.
Скончался 31 октября 2016 г. в Москве на 102-м году жизни. Похоронен с воинскими почестями 3 ноября 2016 г. на Новодевичьем кладбище Москвы.
Народный артист СССР (1975). Лауреат Государственной премии СССР (1951), премий "Кинотавр" (1995), "Кумир" (2000), "Хрустальная Турандот" (2001, 2005), "Золотая маска" (2010), "Ника" (2013). Награжден орденами Трудового Красного Знамени (1947, 1968, 1980) и Дружбы (1995), полный кавалер ордена "За заслуги перед Отечеством" (2000, 2005, 2010, 2015).
Был трижды женат. С 1964 г. супругой актера являлась Иветта Евгеньевна Капралова, журналист и концертная ведущая.