С 1972 г. — на комсомольской и партийной работе: до 1977 была сначала заведующей отделом, затем секретарем, затем первым секретарем Петроградского райкома комсомола Ленинграда.
В 1977–1984 была секретарем, затем — вторым секретарем, затем — первым секретарем Ленинградского обкома ВЛКСМ.
В 1984–1986 гг. — первый секретарь Красногвардейского райкома КПСС Ленинграда.
С 1986 по 1989 г. — заместитель председателя исполкома Ленинградского Совета народных депутатов (курировала вопросы культуры и образования).
В марте 1989 г. была избрана народным депутатом СССР (по квоте общественных организаций — от Комитета советских женщин), с июня 1989 — член Верховного Совета СССР.
В 1989–1991 гг. — председатель комитета Верховного Совета СССР по делам женщин, охраны семьи, материнства и детства, член президиума ВС (по должности).
В 1990 г. — слушатель Курсов усовершенствования руководящих дипломатических работников при Дипломатической Академии МИД СССР.
С мая 1991 по 1995 г. — Чрезвычайный и Полномочный Посол СССР (затем — РФ) в Республике Мальта.
В сентябре 1992 г. вместе с Виктором Кротовым, Ольгой Савельевой (жена Александра Савельева, с 2001 г. председателя правления банка «Санкт-Петербург») и др. выступила соучредителем петербургского ЗАО «Комавтосервис» (20 % уставного фонда); гендиректором которого стал В.Кротов. 1 июля 1993 г. учредила АОЗТ «Валентина», значилась его руководителем (оставаясь одновременно послом на Мальте).
17 июля 1995 г. была назначена директором Департамента по связям с субъектами федерации, парламентом и общественно-политическими организациями МИД РФ.
В сентябре 1997 была назначена Чрезвычайным и Полномочным Послом РФ в Греческой Республике.
24 сентября 1998 г., после отказа Владимира Рыжкова возглавить в кабинете Евгения Примакова социальный блок, указом президента Ельцина была назначена заместителем председателя правительства РФ. Курировала социальный блок. Позже была включена в состав президиума правительства РФ.
25 мая 1999 г. назначена вице-премьером по социальным вопросам в новом правительстве во главе с Сергеем Степашиным. 19 августа 1999 г. — в кабинете Владимира Путина.
В октябре 1999 г. лидеры Экологического движения «КЕДР» заявили, что движение готово поддержать на президентских выборах 2000 г. кандидатуру В.Матвиенко, поскольку она представляется им «единственным по-настоящему искренним и порядочным представителем действующей власти, который по зову сердца проявляет заботу о социальных и экологических проблемах страны», а также «свободна от обязательств перед какими бы то ни было олигархическими кланами».
3 февраля 2000 г. была выдвинута группой избирателей кандидатом на пост президента РФ, но баллотироваться не стала.
10 марта 2000 г. объявила о вступлении в избирательную кампанию по выборам губернатора Санкт-Петербурга.
В марте 2000 г. Сергей Станкевич сделал заявление о решении «Союза правых сил» (СПС) поддержать на выборах губернатора Санкт-Петербурга В.Матвиенко, однако пресс-служба фракции СПС в Государственной думе опровергла это заявление, отметив, правда, что лидер фракции Сергей Кириенко согласился оказывать ей помощь в ходе предвыборной кампании со стороны штаба по выборам мэра Москвы.
4 апреля 2000 г. после встречи с президентом Путиным заявила, что он попросил ее не регистрироваться кандидатом в губернаторы Санкт-Петербурга. 5 апреля 2000 г. официально отказалась баллотироваться на пост губернатора.
18 мая 2000 г. указом президента Путина была назначена заместителем председателя правительства РФ в кабинете Михаила Касьянова.
11 марта 2003 г. президент Путин освободил В.Матвиенко от должности вице-премьера и назначил ее полномочным представителем президента РФ в Северо-Западном Федеральном округе.
24 июня 2003 г. заявила о намерении баллотироваться на пост губернатора Санкт-Петербурга на выборах, назначенных в связи с переходом Владимира Яковлева на работу в правительство РФ. 22 июля 2003 г. стало известно, что предвыборный штаб В.Матвиенко возглавит ректор Горного института и друг Путина Владимир Литвиненко. 25 июля 2003 г. о поддержке Матвиенко на выборах заявил генсовет партии «Единая Россия».
2 сентября 2003 г. президент Путин на встрече с Матвиенко пожелал ей победы на выборах. В тот же день вице-губернатор Санкт-Петербурга и кандидат в губернаторы Анна Маркова обвинила Путина в незаконной агитации в пользу Матвиенко: «Сколько стоит сняться в политическом рекламном ролике с президентом страны и показать его в федеральном эфире? Оплачен ли он из избирательного фонда депутатом?».
10 сентября 2003 г. в штабе Матвиенко было заявлено, что из-за ситуации с сюжетом о встрече с Путиным руководство канала ТВЦ 7 сентября сняло с эфира программу «Момент истины», которая должна была содержать сюжет о Матвиенко, оплаченный из ее избирательного фонда. 13 сентября 2003 г. городской суд г. Санкт-Петербурга отказался удовлетворить просьбу А.Марковой отменить регистрацию Матвиенко.
16 сентября 2003 г. вице-премьер Владимир Яковлев пожелал Матвиенко успехов на выборах.
В первом туре выборов губернатора Санкт-Петербурга 21 сентября 2003 г. В.Матвиенко набрала 48,61 % голосов избирателей, вместе с ней во второй тур вышла А.Маркова, получившая 15,89 %. Против всех проголосовали 10,97 % избирателей. 5 октября 2003 г. В.Матвиенко победила на выборах губернатора Санкт-Петербурга, набрав 63 % голосов и опередив А.Маркову (24 %).
24 февраля 2004 г. на заседании городского правительства В.Матвиенко предложила выселять жильцов, не оплачивающих коммунальные услуги.
6 декабря 2006 г., во время кампании по выборам нового состава Законодательного Собрания Петербурга, направила Путину заявление с просьбой о досрочном сложении своих полномочий и постановкой вопроса о доверии. 13 декабря 2006 г. Путин внес на рассмотрение ЗакСа старого созыва, где большинство было у фракции ЕР, кандидатуру Матвиенко для наделения ее полномочиями губернатора Петербурга. 20 декабря 2006 г. ЗакС утвердил кандидатуру Матвиенко на пост губернатора города.
В ночь на 18 мая 2007 г., по информации правоохранительных органов, в Петербурге были обезврежены трое членов экстремистской организации петербургских мусульман, якобы готовивших покушение на Матвиенко. В начале 2008 г. на процессе по делу о покушении на Матвиенко прокуратура изложила коллегии присяжных версию следствия. Согласно этой версии, группа молодых мусульман планировала убийство губернатора с целью дестабилизации обстановки с перспективой появления в России исламского государства. 7 апреля 2008 г. присяжные на вопрос о том, имело ли место событие преступления, единодушно ответили «нет». Подсудимые были отпущены из-под стражи.
25 сентября 2007 г. согласилась возглавить в качестве «паровоза» петербургский список «Единой России» на выборах в Госдуму 2 декабря 2007 г. (не вступая при этом в партию). Однако в начале октября выяснилось, что возглавит список Борис Грызлов, а Матвиенко заняла в нем второе место.
22 сентября 2009 г. правительство Санкт-Петербурга разрешило контролируемому «Газпром нефтью» ОАО «Общественно-деловой центр "Охта"» построить рядом с историческим центром города 403-метровый офисный небоскреб. Решение, которое сама Матвиенко и глава «Газпрома» Алексей Миллер лоббировали с 2005 г., было принято вопреки протестам общественности. Министерства культуры и ЮНЕСКО. 8 октября 2009 г. министр культуры РФ Александр Авдеев лично выразил протест против строительства небоскреба.
14 октября 2009 г. «Коммерсант» сообщил, что в его распоряжении оказался текст заключения Росохранкультуры о незаконности строительства «Охта-центра», который направил в прокуратуру Санкт-Петербурга министр культуры РФ Авдеев. Из документа следовало, что на территории строительства находится охраняемый законом археологический памятник «Шведская крепость Ниеншанц». В итоге в конце 2010 г. Матвиенко приняла решение отказаться от строительства нарушающего исторические панорамы небоскреба.
На съезде партии «Единая Россия» в ноябре 2009 г. вступила в партию и была избрана членом её высшего совета».
Зимой 2010–2011 гг. в Петербурге выпало большое количество снега. Матвиенко не смогла организовать уборку города от снега, за что критиковалась жителями.
В январе 2011 г. Матвиенко обратилась к премьеру Путину· с просьбой исключить Санкт-Петербург из списка исторических поселений, который предусматривает жесткий федеральный контроль над сохранением всех исторически ценных градоформирующих объектов и обязывает местные власти согласовывать с Росохранкультурой градостроительные проекты. Это вызвало волну протеста среди горожан.
24 июня 2011 г. глава Башкортостана Рустэм Хамитов выдвинул идею назначить Матвиенко председателем Совета Федерации вместо Сергея Миронова. Кандидатуру Матвиенко поддержал президент Медведев, но, чтобы попасть в СФ, надо было победить на каких-нибудь местных выборах. Поэтому Матвиенко приняла участие в довыборах в муниципалитеты муниципальных образований «Петровский» и «Красненькая речка» города Санкт-Петербурга и одержала победу, набрав соответственно 95,61 % и 97,29 % голосов избирателей. Различные оппозиционные партии внимательно отслеживали назначение довыборов, ожидая выдвижение Матвиенко и надеясь выставить против неё своих кандидатов, но о выборах в Петровском и Красненькой речке стало широко известно, когда выдвижение кандидатов уже завершилось (муниципальные газеты с объявлением о выборах были напечатаны задним числом)[71].
31 августа 2011 г. губернатор Санкт-Петербурга Георгий Полтавченко подписал постановление об её назначении членом Совета Федерации Федерального Собрания Российской Федерации — представителем в Совете Федерации Федерального Собрания Российской Федерации от исполнительного органа государственной власти города Санкт-Петербурга.
21 сентября 2011 г. Матвиенко голосами 140 депутатов при 1 воздержавшемся была избрана председателем СФ РФ. Голосование было безальтернативным.