В гимназические годы Вышинский впервые приобщился к революционной среде, активно участвуя в антисамодержавных сходках. Поступив в 1901 году на юридический факультет Киевского университета, он еще более проникся революционным духом. За это уже через несколько месяцев, в марте 1902 года, его в числе нескольких других студентов отчислили из университета без права повторного поступления и он попал под полицейский надзор. Вышинский возвратился в Баку. В 1903 году он вступил в бакинскую организацию РСДРП. По духу ему больше пришлись меньшевики, к которым он и примкнул. Занимая весьма скромную должность бухгалтера в магазине, он настойчиво занимался революционной работой. Темпераментного и красноречивого бухгалтера очень быстро заметили не только в революционной среде. В 1906–1907 годах Вышинского дважды арестовывали, но каждый раз, после непродолжительного заключения, освобождали за недостаточностью улик. Однако в апреле 1908 года под кличкой Рыжий он был осужден Тифлисской судебной палатой к одному году заключения в крепости. Наказание он отбывал в Баиловской тюрьме, где в то время находился известный революционер Коба (И. В. Сталин). Какое-то время они даже сидели в одной камере.

После освобождения из тюрьмы Андрей Вышинский решил немного остепениться, так как его семья к тому времени увеличилась — родилась дочь Зинаида. Он переехал в Киев, где надеялся завершить свое образование. Ему удалось вновь стать студентом и окончить университет. Вскоре Вышинский уехал в Баку. Некоторое время он перебивался частными уроками и газетно-репортерской деятельностью, но такая работа не удовлетворяла его честолюбия. В 1915 году он появляется в Москве. Здесь ему удалось поступить помощником к знаменитому адвокату, занимавшемуся преимущественно политическими делами, — Павлу Николаевичу Малянтовичу.

Адвокатская карьера А. Я. Вышинского была непродолжительной — менее двух лет. После Февральской революции 1917 года он становится председателем Якиманской районной управы и комиссаром милиции, ревностно выполняя все указы Временного правительства, в том числе и по розыску В. И. Ленина, скрывавшегося от властей после июльских событий 1917 года.

После Октябрьской революции Вышинский формально не примкнул к партии большевиков. Тем не менее, в отличие от многих своих соратников-меньшевиков, не выступал открыто против новой власти. Это дало ему возможность устроиться, если не с комфортом, то во всяком случае неплохо. Он сумел попасть на службу инспектором в Московское продовольственное управление и постепенно, благодаря дружеским связям с выходцем из Баку большевиком А. Б. Халатовым, ставшим в Москве чрезвычайным комиссаром по продовольствию и транспорту, а также поддержке Сталина, за несколько лет сделал неплохую карьеру. В 1919 году его назначают начальником управления по распределению в Наркомпроде, а осенью того же года временно откомандировывают в Тулу в распоряжение политотдела Южного фронта, где Вышинский работает снабженцем. В 1920 году он вступает в Российскую коммунистическую партию большевиков, что открывает перед ним новые возможности еще более высокого служебного роста.

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