В Советской Армии, ВС СССР, с 1967 года.
Окончил Московское высшее общевойсковое командное училище имени Верховного Совета РСФСР в 1971 году.
С 1971 года командовал мотострелковым взводом и мотострелковой ротой в Белорусском военном округе, затем — командир мотострелкового батальона в Центральной группе войск на территории Чехословакия.
В 1978 году окончил Военную академию имени М. В. Фрунзе.
С 1978 года — старший офицер оперативного отдела штаба армии.
С 1979 года служил в частях Забайкальского военного округа, расквартированных на территории Монголии — начальник штаба мотострелкового полка, командир мотострелкового полка, начальник штаба мотострелковой дивизии.
С 1985 года — командир мотострелковой дивизии в том же Забайкальском военном округе, но уже на территории Бурятской АССР.
За период офицерской службы получил досрочно три воинских звания.
В 1992 году — окончил Военную академию Генерального штаба Вооруженных сил Российской Федерации.
С 1992 года — начальник штаба 6-й Армии в Ленинградском военном округе, с 1994 года — командующий 6-й Армией (общевойсковой) в том же округе.
С декабря 1996 года — 1-й заместитель командующего войсками Забайкальского военного округа.
С апреля 1998 года — начальник штаба — 1-й заместитель командующего войсками Забайкальского военного округа.
1 декабря 1998 года было произведено объединение Сибирского военного округа и Забайкальского военного округа в единый Сибирский военный округ с штабом в Чите, а генерал В. А. Болдырев назначен начальником штаба — 1-м заместителем командующего войсками этого округа.
С 28 марта 2001 года — командующий войсками Сибирского военного округа.
С 18 декабря 2002 года — командующий войсками Северо-Кавказского военного округа.
Воинское звание генерал армии присвоено указом Президента Российской Федерации В. В. Путина от 12 декабря 2003 года.
19 июля 2004 года переведён на должность командующего войсками Приволжско-Уральского военного округа. В военных кругах высказывалось мнение по поводу этого перемещения, что Болдырев, ранее никогда не участвовавший в боевых действиях, не смог обеспечить эффективное проведение контртеррористической операции на Северном Кавказе, в которой основную роль играли войска его округа. Дополнительным доводом в пользу этой версии служит то, что Болдырев был перемещён в тыловой военный округ через несколько дней после ставшего полной неожиданностью нападения чеченских боевиков на Назрань (см. Рейд на Ингушетию (2004)).
С 31 июля 2008 года — Главнокомандующий Сухопутными войсками Российской Федерации.
14 декабря 2009 г. контракт о военной службе В.А.Болдырева был продолжен, но вскоре 1 января 2010 г. главком сухопутных войск написал рапорт об увольнении, документ бым подписан примерно через 2-3 месяца.