Родился 20 ноября 1952 года в городе Касли Челябинской области в семье рабочего.
Учился вкаслинской средней школе № 27. В 1971 году окончил Свердловское суворовское военное училище. В 1975 году окончил Рязанское высшее воздушно-десантное командное училище. В 1985 году окончил Военную академию им. Фрунзе. В 1994 году окончил Академию Генерального штаба ВС РФ.
В декабре 1979 года участник боевых действий в составе ограниченного контингента Советских войск в Афганистане, командир роты, принимал участие в штурме дворца Таджи-Бек (дворец Амина) в Кабуле. В 1985 году служил в Кишиневе командиром десантного полка в звании гвардии подполковника. С 1986 по 1989 год командир 345-го отдельного гвардейского парашютно-десантного полка. В 1986 году вернулся в Афганистан командиром полка. С 1989 по 1992 год командир 98-й гвардейской воздушно-десантной дивизии. В 1990 году назначен заместитель министра РФ по делам гражданской обороны, чрезвычайным ситуациям и ликвидации последствий стихийных бедствий. С 1992 по 1994 год слушатель Военной академии Генерального штаба. С 1994 год по 2003 год работал заместителем Министра Российской Федерации по делам гражданской обороны, чрезвычайным ситуациям и ликвидации последствий стихийных бедствий.
В 2003 году был избран депутатом Государственной Думы ФС РФ четвертого созыва от избирательного объединения Партия «ЕДИНСТВО» и «ОТЕЧЕСТВО» — Единая Россия.Член фракции «Единая Россия».Член Комитета ГД по безопасности.
C 27 февраля 2007 года является Председателем Совета Московского городского отделения Всероссийской общественной организации ветеранов “Боевое Братство”.
В 2007 году был избран депутатом Государственной Думы ФС РФ пятого созыва в составе федерального списка кандидатов, выдвинутого Всероссийской политической партией «ЕДИНАЯ РОССИЯ». Член фракции «ЕДИНАЯ РОССИЯ».
Награжден орденами Ленина, Красного Знамени, орден Мужества, двумя орденами Красной Звезды орденом «За службу Родине в Вооруженных Силах СССР» III степени и орденом и медалями Республики Афганистан. С 1980 года Герой Советского Союза. В 1988 году было присвоено звание Героя Советского Союза. Генерал-полковник. В 1988 году Валерию Востротину присвоено звание Почетного гражданина Каслей. В 1999 году присвоено звание генерал-полковника.
Исполнил главную роль в художественном фильме «Черная акула».
Женат, есть дочь.