Родился в Кривом Роге (Украина). В 1986 году закончил Московское хореографическое училище по классу профессора Петра Пестова и был принят в труппу Московского классического балета под руководством Наталии Касаткиной и Владимира Василёва. Являясь премьером труппы, исполнял партии в балетах классического наследия «Жизель» (Альберт), «Лебединое озеро» (Принц Зигфрид), «Дон Кихот» (Базиль, Гамаш), в балете Джорджа Баланчина «Тема с вариациями», в постановках Наталии Касаткиной и Владимира Василёва «Сотворение мира» (Адам), «Ромео и Джульетта» (Ромео, Меркуцио), во многих сочинениях руководителей театра был первым исполнителем главных ролей.
В 1992 году стал ведущим солистом балета Венской государственной оперы, где танцевал ведущие партии в спектаклях «Дон Кихот» в постановке Михаила Барышникова и Елены Чернышевой, «Сон в летнюю ночь» Джона Ноймайера, «Манон» Кеннета Макмиллана, «Лебединое озеро» в постановке Рудольфа Нуреева, «Аполлон» Джорджа Баланчина, «Щелкунчик» Юрия Григоровича. С 1994 года — солист Национального балета Канады, где в его репертуар вошли ведущие партии в балетах «Жизель» и «Лебединое озеро» в постановке Эрика Бруна.
В 1995 году Владимир Малахов дебютировал в Американском театре балета, репертуар танцовщика в этой труппе пополнили главные партии в спектаклях «Шопениана» Михаила Фокина, «Баядерка» в постановке Натальи Макаровой, «Этюды» Харальда Ландера, «Вариации на темы Гайдна» Твайлы Тарп, Rеmanso и Without Words Начо Дуато.
Владимир Малахов выступал с балетными труппами Римской оперы, Берлинской государственной оперы, Балета Токио, Штутгартского балета. Его репертуар включает как балеты классического наследия и шедевры ХХ века, так и целый ряд постановок, созданных специально для Владимира Малахова Сашей Вальц, Патрисом Бартом, Мауро Бигонзетти.
В качестве хореографа Владимир Малахов дебютировал в 1999 году, представив свою версию «Баядерки» на сцене Венской государственной оперы (в 2002 году спектакль был поставлен в Берлинской государственной опере). В 2001 году в Вене состоялась премьера спектакля Малахова «Верди балет: маскарад» на музыку Джузеппе Верди.
В 2002-2014 годах Владимир Малахов возглавлял Государственный балет Берлина (до 2004 года – балет Берлинской государственной оперы), для которого создал постановки балетов «Спящая красавица» (2005), «Пери» (2010).
