С 1993 г. — соучредитель АОЗТ «Хокуто» (среди соучредителей: Ау-во Нииникето — друг и коммерческий партнер Бориса Ротенберга).
С 1993 г. — соучредитель ТОО «ВиТ» (вместе с женой Татьяной).
С 1994 г. — соучредитель ООО «Охранное предприятие «Антей».
С декабря 1995 г. — директор государственного учреждения «Комплексная школа высшего спортивного мастерства» в Санкт-Петербурге.
В 1999–2001 гг. принимал активное участие в создании политической партии «Единство», предшественницы и основной составляющей будущей «Единой России».
С 2002 г. — директор Всемирной Федерации кобудо по России, также возглавляет региональную федерацию боевых искусств «Будо».
С 2003 г. — президент Российской Федерации джиу-джитсу.
Намеревался баллотироваться в Государственную думу в 2003 г. при поддержке Народной партии Российской Федерации (НПРФ) Геннадия Райкова.
С 2003 г. — член Социалистической единой партии России («Духовное наследие», СЕПР) Алексея Подберезкина, член генерального совета партии.
В 2003 г. учредил с Аркадием Ротенбергом Автономную некоммерческую организацию «Детско-юношеский спортивный клуб «Явара-М» и стал президентом клуба.
В 2003 г. был включен в состав Совета по физической культуре и спорту при полномочном представителе президента РФ в Северо-Западном федеральном округе Викторе Черкесове. В состав совета также входил Александр Бастрыкин.
Осенью 2003 г. был выдвинут избирательным блоком «Родина» (лидеры — Дмитрий Рогозин и Сергей Глазьев) кандидатом в депутаты Государственной думы РФ четвертого созыва по общефедеральному списку блока (№ 1, региональная группа «Старорусская»). 7 декабря 2003 г. был избран депутатом Государственной думы. Зарегистрировался во фракции «Родина». Был членом комитета думы по физической культуре и спорту.
В борьбе между Рогозиным и Глазьевым за влияние в блоке «Родина» в начале 2004 г. поддержал Рогозина.
14 февраля 2004 г. избран председателем Генерального совета СЕПР.
В 2005 г. был членом совета директоров ОАО «Н1111 «Радар ммс» (председатель совета директоров — Кретов Александр Владимирович, вице-президент ОАО «Банкирский дом СПб»; генеральный директор — Анцев Георгий Владимирович).
В июле 2005 г. во внутрифракционном конфликте Дмитрия Рогозина и Сергея Бабурина поддержал Бабурина. Вошел в созданную им новую думскую фракцию «Народно-Патриотический союз «Родина» («Народная воля — СЕПР»)».
В декабре 2005 г. Сергей Бабурин и Шестаков провели заседание высшего совета блока «Родина», на котором было принято решение исключить из состава совета всех членов партии Дмитрия Рогозина и его самого и обратиться в Минюст с требованием аннулировать регистрацию других организаций с названием «Родина». Это название, по мнению Бабурина и Шестакова, должно было принадлежать их партиям.
В 2006 году Бабурин и Шестаков подписали документ о намерениях объединить партии НВ и СЕПР в единую партию «Народнопатриотический союз», но эта идея не была реализована.
В декабре 2006 г. Шестаков высказал свое несогласие с произошедшими кадровыми перестановками во фракции Народно-Патриотический союз «Родина», а именно с избранием ее руководителем Геннадия Семигина, лидера «Патриотов России». В письме в адрес Сергея Бабурина
Шестаков, отсутствовавший на заседании фракции, заявил, что возражает против избрания Семигина руководителем фракции, против увеличения числа сопредседателей фракции и против ее переименования.
В апреле 2007 г. лидер партии «Справедливая Россия» Сергей Миронов и Шестаков подписали соглашение о политическом союзе «Справедливой России» и СЕПР. В мае 2007 г. СЕПР приняла решение о самоликвидации и вхождении ее членов в состав партии «Справедливая Россия».
В 2007 г. был избран депутатом Государственной думы пятого созыва по федеральному списку кандидатов Политической партии «Справедливая Россия: Родина/Пенсионеры/Жизнь» (№ 2 в региональной группе по Санкт-Петербургу). Был заместителем руководителя фракции «Справедливая Россия». Был членом комитета по физической культуре и спорту.
В 2008 г. возглавил консультативный совет агрохолдинга «Агроинвест».
5 ноября 2009 г. избран президентом Международной Федерации самбо (FIAS).
В июле 2011 г. в Санкт-Петербурге участвовал в праймериз «Единой России» от Общероссийского народного фронта, занял 20-е место.
В августе 2011 г. Шестаков сообщил о своем вступлении в ОНФ. 10 августа 2011 г. партия «Справедливая Россия» исключила из своих рядов депутатов Государственной думы, вступивших в «ОНФ», в том числе и Шестакова.
В 2011 г. был избран депутатом Государственной думы шестого созыва по избирательному списку партии «Единая Россия» (№ 7 в региональной группе по Санкт-Петербургу). Член фракции «Единая Россия». Член комитета по физической культуре, спорту и делам молодежи.
В 2015 г. учредил Фонд содействия развитию науки и спорта «Ток-совская перспектива» (соучредители: Патрушев Алексей Викторович, племянник Николая Патрушева, и Шульга Сергей Николаевич).