К тому времени Степан уже был членом Украинской военной организации (УВО), образованной в 1920 г. из отрядов Сечевых Стрельцов во главе с Евгением Коновальцем. По заданию УВО Бандера вел пропаганду в родном и соседних селах. В стихию подпольной работы он окунулся, едва поступив на агрономический факультет Львовского политехнического института. Хотя Степан честно старался учиться, диплом инженера-агронома он так и не получил: помешала политическая деятельность и арест.
В 1929 г. завершился процесс объединения всех националистических организаций Западной Украины в единую Организацию украинских националистов. Проводником (руководителем) ОУН был избран Евгений Коновалец, а созданная ранее УВО вошла в ОУН как одно из подразделений. Членом новой организации Бандера стал с начала ее существования. Имея уже опыт революционной деятельности, он руководил распространением подпольной литературы, которую печатали за пределами Польши. На этот период приходятся его первые аресты, ставшие школой политической борьбы.
Вскоре Степан Бандера вошел в состав Краевой Экзекутивы (исполнительного органа) ОУН, заняв пост секретаря отдела пропаганды в Западной Украине. Он действительно поднял пропаганду национальной идеи на высокий уровень. Начались массовые акции, которые преследовали цель пробуждения политической активности народа. В частности, Бандера задумал и провел «Школьную акцию», когда ученики выбрасывали из школ польские гербы и флаги, отказывались отвечать на польском языке и бойкотировали учителей-поляков. «Антимонопольная акция» представляла собой отказ украинцев покупать водку и табак. ОУН призывала: «Прочь из украинских сел и городов водку и табак, потому что каждый грош, потраченный на них, увеличивает фонды польских оккупантов». Польские газеты немедленно представили это как очередное доказательство украинского антисемитизма: ведь держателями питейных заведений, как правило, были евреи.
Для проведения подобных акций требовались немалые средства. Поэтому боевики ОУН, находясь в состоянии войны с польским государством, часто грабили банки и почтовые отделения. При этом иногда погибали случайные прохожие. Естественно, что такие действия наносили удар по имиджу организации. Поняв это, Степан Бандера запретил акции экспроприации. Решено было сосредоточиться на политической пропаганде.
В начале 1933 г. конференция Провода ОУН в Праге утвердила Степана Андреевича на посту краевого проводника. Началась серьезная работа по расширению структуры ОУН и организации подпольной учебы кадров. Чтобы еще раз напомнить о целях борьбы с режимом, была проведена серия карательных акций против представителей польской власти. Два наиболее известных политических убийства того времени получили широкую огласку в мире. 21 октября 1933 г. 18-летний студент Мыкола Лемык убил сотрудника советского консульства в Львове А. Майлова, заявив, что пришел отомстить за голодомор в Украине, устроенный большевиками. Этим политическим убийством руководил лично Бандера. Суд над Лемыком дал возможность заявить, что голод в Украине – действительный факт.
Еще одной жертвой мести ОУН стал министр внутренних дел Польши Бронислав Перацкий. Решение о его устранении было принято на специальной конференции ОУН в Берлине, где присутствовал Андрей Мельник– представитель Провода Украинских националистов и краевой проводник Степан Бандера. Убийство было актом возмездия за проведенную в 1930-1932 гг. под руководством Перацкого операцию «пацификации» (умиротворения), когда в результате действий польской полиции и армии были разрушены и сожжены сотни сел, убиты несколько тысяч жителей Галичины и Волыни. План покушения разработал Роман Шухевич, приводил его в действие Мыкола Лебедь, общее руководство осуществлял Степан Бандера. Организатор и исполнитель покушения были арестованы, а кроме них – еще 10 человек, обвиненных в подготовке преступления.
Два года длилось следствие. Бандеру содержали в одиночной камере закованным в кандалы. На суде во Львове обвиняемые отказывались говорить по-польски, здоровались приветствием «Слава Украине!» и превратили зал процесса в трибуну пропаганды идей ОУН. Степана Бандеру, Мыколу Лебедя и Ярослава Карпинца суд приговорил к смертной казни. По амнистии, объявленной ранее, высшую меру заменили пожизненным заключением. Несколько попыток подготовить побег Бандеры из тюрьмы не имели успеха. За решеткой он просидел до 1939 г. Когда Германия напала на Польшу, городок, в котором находилась тюрьма, подвергся бомбардировке. Тюремная охрана разбежалась, а Степана Бандеру выпустили из камеры освободившиеся заключенные-украинцы.
Оказавшись на свободе, Бандера прибыл во Львов. За несколько дней до этого город был занят Красной Армией. Поначалу находиться там было относительно безопасно. На протяжении нескольких недель происходила разработка стратегии будущей борьбы. Продумывался план действий на случай массовых репрессий и депортаций советскими войсками населения Украины.