Протестные действия студентов обычно сопровождались забастовками, обструкциями, сходками. За участие в них через несколько месяцев, в марте 1902 года, Андрея Вышинского в числе других марксистски настроенных студентов отчислили из университета без права повторного поступления. Вышинский возвратился в Баку и там в 1903 году вступил в организацию РСДРП. По духу ему больше пришлись меньшевики, к которым он и примкнул. Вскоре его имя становится довольно известным в городе. Он ведет активную революционную пропаганду среди рабочих электростанции на Баиловом мысу, Кокоревских и Монташевских промыслов и промыслов акционерного общества «Олеум».

Пик революционной активности Вышинского приходится на 1905 год. В феврале этого года, он создал боевую дружину, которая насчитывала сотни рабочих, как от большевиков, так и от меньшевиков, выступившую против жестокой армяно-татарской резни, а в период октябрьской стачки и декабрьской забастовки вел работу среди железнодорожников и входил в стачечный комитет. В то время он занимал весьма скромную должность бухгалтера в магазине. Будучи темпераментным и красноречивым оратором, он часто выступал на митингах и собраниях со страстными речами, громя в них самодержавие, эсеров, черносотенцев и их сторонников.

В 1906—1907 годах Вышинского дважды арестовывали, но каждый раз после непродолжительного заключения освобождали за недостаточностью улик. Тогда же, по его словам, он и его жена, Капитолина Исидоровна подверглись нападению черносотенцев и, как отмечалось в ранних биографиях Вышинского, были даже ранены.

В апреле 1908 года Вышинский под кличкой Рыжий был осужден Тифлисской судебной палатой по статье 129 Уголовного уложения, предусматривавшей ответственность за произнесение или чтение публично речи или сочинения, возбуждающего к ниспровержению существующего строя. Его приговорили к одному году заключения в крепости. Наказание он отбывал в Баиловской тюрьме, где в то время находился известный революционер Коба, или И. В. Сталин. Они даже сидели в одной камере.