11 мая 1931 года Вышинский был назначен Прокурором РСФСР, сменив на этом посту Н. В. Крыленко, ставшего народным комиссаром юстиции республики. Об Андрее Януарьевиче заговорили как о новой восходящей звезде на юридическом небосклоне.

20 июня 1933 года ЦИК и СНК СССР приняли постановление «Об учреждении Прокуратуры Союза ССР». Первым Прокурором СССР был назначен известный государственный и политический деятель Иван Алексеевич Акулов, который не был юристом и не имел высшего образования. А. Я. Вышинский стал его заместителем.

Одним из первых громких дел, в расследовании которого принял участие Вышинский уже в новом качестве, было дело об убийстве члена Президиума ЦИК СССР и Политбюро ЦК ВКП(б) С. М. Кирова.

3 марта 1935 года ЦИК СССР назначил Вышинского Прокурором СССР. Вышинский услужливо и безропотно выполнял роль главного инквизитора вождя. Он завладел всеми ключевыми позициями юридической науки и практики. Бывший прокурор РСФСР А. А. Волин, работавший с Вышинским, рассказывал, что в то время «всюду был слышен голос только его одного. Вообще говоря, Андрей Януарьевич настолько мог приспосабливаться к ситуации, что даже в наступившее демократическое время вполне пробился бы во власть, причем играл бы не последнюю скрипку».

В декабре 1937 года состоялись выборы в Верховный Совет СССР, а 12 января 1938 года открылась его 1-я сессия. В последний день сессии А. Я. Вышинский был вновь назначен Прокурором Союза ССР сроком на семь лет (по новой Конституции СССР). От имени Совета Старейшин Совета Союза и Совета Национальностей его кандидатуру представил депутат Г. И. Петровский. В своей речи он сказал, что Вышинский всем «известен по своим выступлениям на судебных процессах против врагов народа, разоблаченных нашими славными органами Наркомвнудела под руководством Николая Ивановича Ежова».

21–22 мая 1938 года в Москве прошло очередное Всесоюзное совещание прокуроров. Доклад, как всегда, сделал А. Я. Вышинский. Лейтмотивом его выступления был вопрос о перестройке работы органов прокуратуры в соответствии с требованиями новой Конституции СССР. Хотя перестройку он понимал весьма своеобразно, что наглядно показывает даже такой небольшой отрывок из доклада.

«Едва ли найдется хоть один честный работник в системе прокуратуры, который не сознавал бы со всей очевидностью этой жгучей потребности – перестроить всю систему нашей работы, – сказал он. – Нет ни одного честного прокурорского работника, который не ощущал бы в самой резкой форме необходимости окончательно добить, я бы сказал, затесавшихся в наши ряды врагов, вырвать с корнем изменников и предателей, которые, к сожалению, оказались и в среде прокурорских работников. Пересмотреть отношение к работе каждого из наших работников, даже в том случае, если он не поколебал к себе политического доверия, пересмотреть, следовательно, всю систему нашей работы, всю методику нашей работы для того, чтобы с обновленными уже в значительной степени кадрами взяться по-настоящему, по-большевистски за решение задач, которые с такой остротой, силой и требовательностью стоят перед нами, – вот в чем заключается смысл и сущность перестройки нашей работы».

В докладе Вышинский много внимания уделил общему надзору прокуратуры, следствию, подготовке прокурорско-следственных кадров. Говоря о «вредительстве» в области права, не преминул пнуть уже арестованного бывшего наркома юстиции СССР Н. В. Крыленко, который «проводил», по его словам, в своих статьях и книгах «вредительские взгляды и мыслишки». Происходивший в стране разгул репрессий в отношении простых людей Вышинский пытался изобразить как происки пробравшихся в органы «враждебных элементов», которые «преступной работой» подрывали авторитет «советского правопорядка». С этой целью он привел ряд действительно вопиющих случаев нарушения законности и необоснованного возбуждения уголовных дел.