Причастность Бандеры к убийству Перацкого, со ссылкой на убитого им Коновальца, подтверждает и Павел Судоплатов. В своих мемуарах он пишет: «Полной неожиданностью явилась для меня и новость, что убийство польского министра генерала Перацкого в 1934 г. украинским террористом Мацейко было проведено вопреки приказу Коновальца, и стоял за этим Бандера, соперничавший с последним за власть. Бандера стремился к контролю над организацией, играя на естественной неприязни украинцев к Перацкому, который нёс ответственность за репрессии против украинского меньшинства в Польше. Коновалец рассказал мне, что к этому времени между Польшей и Германией был подписан договор о дружбе, так что немцев никоим образом не устраивали любые враждебные акции по отношению к полякам. Они были так взбешены, что выдали Бандеру, скрывавшегося в Германии».
В 1934 г. Бандера был арестован польскими властями, а в ноябре 1935 г. в Варшаве начался суд над ним и одиннадцатью другими украинскими националистами. Их обвиняли не только в соучастии в убийствах, но и в совершении «эксов» — нападении на почтовые дилижансы, кассы и банки. В ответ на замечание прокурора, что боевая деятельность ОУН противоречит основам христианской морали, Бандера возложил моральную ответственность за действия украинских боевиков на польские власти, которые, «растоптав Божьи и человеческие законы, поработили украинский народ и создали положение, при котором (он) вынужден убивать палачей и предателей».
13 января 1936 г. Степан Бандера, Микола Лебедь и Ярослав Карпинец были приговорены к смертной казни через повешение, остальные подсудимые — к тюремному заключению на срок от 7 до 15 лет. От виселицы приговорённых спасла амнистия, принятая во время процесса. Казнь была заменена пожизненным заключением. Во время суда в Варшаве боевики ОУН во Львове убили профессора Львовского университета Ивана Бабия и студента Якова Бачинского, обвинённых националистами в связях с польской полицией. Экспертиза показала, что жертвы этого убийства и Бронислав Перацкий были застрелены из одного револьвера. Это позволило польским властям организовать над Бандерой и рядом его соратников ещё один судебный процесс, на сей раз во Львове. 25 мая 1936 г. Бандера наряду с другими членами Краевой экзекутивы ОУН (всего 27 человек) предстал перед судом по обвинению в руководстве террористической деятельностью ОУН-УВО. Своей причастности к гибели Бабия и Бачинского он не отрицал — их убили по его личному приказу за сотрудничество с польской полицией. На процессе Бандера также заявил, что ОУН занимает негативную позицию по отношению к коммунизму. Объясняя цели и методы борьбы организации против большевистской идеологии, Бандера в частности сказал: «Большевизм — это система, с помощью которой Москва поработила украинскую нацию, уничтожив украинскую государственность». На Львовском процессе Бандера был приговорён к пожизненному заключению. В 1936–1939 гг. он отбывал срок в польских тюрьмах. Во время заключения, познакомившись с работами идеолога украинского национализма Дмитрия Донцова, Бандера пришёл к выводу — ОУН недостаточно «революционна» по своей сути, и это необходимо исправить.
Степан Бандера вышел на свободу из Брестской крепости 13 сентября 1939 г., после нападения Германии на Польшу. По утверждению Бандеры, во время наступления немцев польские охранники оставили тюрьму и его камеру открыли заключённые. «На самом деле Бандеру освободили немцы, что подтверждают асы гитлеровских спецслужб Отто Скорцени, Вальтер Шелленберг, Эрвин Штольце и другие. Но националисты отрицают этот факт, так как он подтвердит тесное сотрудничество ОУН с нацистами. Германская разведка и ранее предпринимала попытки освободить Бандеру, который в секретной картотеке абвера значился под псевдонимом Серый. Оказывалось дипломатическое давление, готовился побег с участием десанта, план которого разрабатывал Шухевич».
Около двух недель Бандера находился в подполье на советской территории, где установил контакт с активистами ОУН, с которыми обсуждал планы по созданию сети ОУН на территории всей Украины и развёртыванию борьбы против советских властей. Опасаясь задержания сотрудниками НКВД, во второй половине октября 1939 г. Бандера пересёк советско-немецкую демаркационную линию и прибыл в Краков, где активно включился в деятельность ОУН. 3 июня 1940 г. в Кракове Степан Бандера женился на Ярославе Опаривськой.
В ОУН назревал раскол. В августе 1939 г. на II Большом сборе ОУН в Италии Андрей Мельник был провозглашён преемником убитого в Роттердаме лидера организации Евгения Коновальца. Однако часть делегатов съезда высказалась против избрания Мельника, отдав предпочтение Бандере. Точки зрения Мельника и Бандеры на стратегию ведения освободительной борьбы имели принципиальные различия. Бандера считал, что в борьбе необходимо рассчитывать в первую очередь на собственные силы, поскольку в независимости Украины, по его убеждению, никто не был заинтересован. Возможный союз с Германией он рассматривал как временный и выступал «за то, чтобы поставить немцев перед фактом — признать Украинское Самостоятельное Государство».
Мельник же считал, что ставку следует делать на нацистскую Германию, а вооружённое подполье создавать ни в коем случае не следует.
10 февраля 1940 г. Бандера созвал в Кракове некоторых лидеров ОУН Галиции и Прикарпатья и, объявив себя законным преемником Коновальца на посту главы организации, создал Революционный провод ОУН. В него вошли его ближайшие единомышленники: Ярослав Стецько, Степан Ленкавский, Николай Лебедь, Роман Шухевич и Василий Охримович. В апреле 1940 г. на встрече с Бандерой в одном из городов на севере Италии Мельник отверг предложение о разрыве связей с Германией. Он не согласился также сместить с ключевого поста в ОУН Ярослава Барановского, которого сторонники Бандеры обвиняли в некоторых неудачах ОУН. Произошёл исторический раскол ОУН на две фракции — ОУН(б) (бандеровцы) и ОУН(м) (мельниковцы). В апреле 1941 г. Революционный провод созвал так называемый Большой сбор ОУН, единогласно избравший Степана Бандеру проводником ОУН(б). Прогнозировавший скорый военный конфликт между СССР и нацистской Германией, Бандера начал подготовку к вооружённой борьбе украинских националистов против Москвы. ОУН(б) начала проводить организационную работу на украинских землях, сформировала три походные группы, организовала сеть территориальных подпольных организаций. В Киеве и Львове были сформированы руководящие центральные органы для предстоящих действий.
Перед самым началом Великой Отечественной войны Бандера инициировал создание Украинского национального комитета для консолидации борьбы всех подконтрольных ОУН(б) сил, а также создание Легиона украинских националистов в составе батальонов «Нахтигаль» и «Роланд», военнослужащие которых в будущем составили ядро Украинской повстанческой армии. 30 июня, в день захвата немцами Львова, в город вошли и бойцы батальона «Нахтигаль» во главе с Романом Шухевичем. В тот же день от лица руководства ОУН(б) Ярослав Стецько зачитал «Акт возрождения Украинского государства», сообщавший о создании «нового украинского государства на материнских украинских землях». В последующие несколько дней представители ОУН(б) сформировали исполнительный орган — Украинское государственное правление (УГП), организовали Национальное собрание, заручились поддержкой греко-католического духовенства, включая митрополита Галицкого Андрея (Шептицкого). Бандеры в это время на месте событий не было, он находился в Кракове.
После нападения Германии на СССР Бандера вместе с другими деятелями украинского националистического движения был арестован немецкими оккупационными властями за попытку провозглашения самостоятельного Украинского государства и помещён под стражу, а в январе 1942 г. отправлен в концлагерь Заксенхаузен.
Это подтвердил 29 мая 1945 г. на допросе в отделе контрразведки «СМЕРШ» 2-й гвардейской танковой армии высокопоставленный сотрудник абвера полковник Эрвин Штольце, который также охарактеризовал отношения Бандеры и Мельника.
Приведём фрагмент стенограммы допроса Эрвина Штольце: «…После окончания войны с Польшей Германия усиленно готовилась к войне против Советского Союза, и поэтому по линии абвера принимались меры по активизации подрывной деятельности, так как те мероприятия, которые проводились через Мельника и другую агентуру, казались недостаточными. В этих целях был завербован видный украинский националист Бандера Степан, освобождённый немцами из тюрьмы, где он содержался польскими властями за участие в террористическом акте против руководителей польского правительства. Кто вербовал Бандеру, я не помню, но последний на связи состоял у меня…Несмотря на то, что во время моей встречи с Мельником и Бандерой оба они обещали принять все меры к примирению, я лично пришёл к выводу, что это примирение не состоится из-за существенных различий между ними. Если Мельник спокойный, интеллигентный чиновник, то Бандера — карьерист, фанатик и бандит…С нападением Германии на Советский Союз Бандера активизировал националистическое движение в областях, оккупированных немцами, и привлёк на свою сторону особо активную часть украинских националистов, по сути, вытеснив Мельника из руководства. Обострение между Мельником и Бандерой дошло до предела…В августе 1941 г. Канарис поручил мне прекратить связь с Бандерой и, наоборот, во главе националистов удержать Мельника… Вскоре после прекращения связи с Бандерой он был арестован за попытку сформировать украинское правительство во Львове. Для разрыва связи с Бандерой был использован факт, что последний в 1940 г., получив от абвера большую сумму денег для финансирования созданного подполья в целях организации подрывной деятельности, пытался их присвоить и перевёл в один из швейцарских банков, откуда они нами были изъяты и снова возвращены Бандере… Причём такой же факт имел место и с Мельником… Допросили Начальник ОКР «СМЕРШ» 2 гв. ТА гвардии подполковник Шевченко. Начальник 2-го отдела ОКР «СМЕРШ» 2 гв. ТА гвардии майор Воротилов через переводчика гвардии капитана Зайцева».