В горуправление Малышев пришел еще в 1993 году, тогда Анатолий Собчак пригласил его на должность заместителя мэра Петербурга, руководителя аппарата мэрии. Вице-губернатором Валерий Иванович проработал с 1996 по 1999 год, координируя деятельность комитета по благоустройству и дорожному хозяйству, комитета по туризму, управления по развитию садоводства и огородничества, комитета физкультуры и спорта, а также ряда других подразделений администрации. Именно этому человеку питерцы обязаны появлением в городе Ледового дворца спорта, монумента героическим защитникам Ленинграда, Ушаковской развязки. Бывший вице-губернатор считался высококлассным специалистом, профессионалом. Как руководитель и организатор, он был на высоте всегда, умел не только создавать свою команду, но и сохранять ее, всегда заботился о подчиненных, из-за чего с ним работали охотно, что называется, не за страх, а за совесть. Коллеги Малышева говорили о нем как об одном из самых ярких, харизматичных политиков Санкт-Петербурга. А также как о человеке, которому оппоненты губернатора систематически и целенаправленно мешали работать. Возможно, именно неординарность личности Валерия Ивановича стала причиной того, что ему досталось больше всех неприятностей. «Быть политиком — дело опасное», — сказал по этому поводу председатель Законодательного Собрания С. Тарасов. Узнав о кончине бывшего вицегубернатора, многие депутаты и «отцы города» испытали самый настоящий шок. Малышева знали как энергичного политического деятеля, человека порядочного, последовательного, настойчивого, всегда отстаивавшего свои позиции и умеющего держать данное слово. Он пользовался большим влиянием не только на депутатов, но и, как поговаривают, на членов правительства. Этот неизменно подтянутый, активный человек производил впечатление здорового. И вдруг. Валерия Ивановича не стало на 52 году жизни.
Так кем же был Валерий Малышев? Обычным коррумпированным чиновником? Или личностью, которая по злой иронии судьбы попала под потоки непозволительной лжи, вылитой на его голову правоохранительными органами, старательно пытающимися отыскать черную кошку в темной комнате и не менее старательно избегающими встречи с ней? Для того чтобы попытаться ответить на эти вопросы, необходимо вернуться почти на 10 лет назад.