Після вбивства Коновальця постало серйозне питання: хто очолить ОУН? У вищих, провідних кадрах було немало видатних особистостей. Серед можливих кандидатур на пост Головного провідника називали Сціборського, Бандеру, Тимчія-Лопатинського. Але один із найближчих співробітників Коновальця Я. Барановський оголосив, що в розмові з ним Коновалець назвав своїм спадкоємцем на випадок, якщо з ним щось трапиться, Андрія Мельника (саме ця версія була висунута прихильниками Бандери). Взагалі-то проти цієї кандидатури спочатку не було ніяких заперечень. Мельник був не лише свояком, а й давнім, ще з часів визвольної боротьби 1917—1920 років, побратимом Коновальця. Щоправда, останні роки він був осторонь націоналістичного руху, але оскільки це була нелегальна діяльність, то рядові члени ОУН знали тільки, що Мельник відбував тюремне ув’язнення і ніяк не пов’язаний із польськими державними колами. Здавалося б, немає нічого дивного в тому, що він і став головою Проводу Організації українських націоналістів.

Проте далі події розвивалися за іншим, незапланованим сценарієм.

1 вересня 1939 року після нападу Німеччини на Польщу почалася Друга світова війна. Бандера в цей час перебував у в’язниці, розташованій у славетній Брестській фортеці. У перший же день війни місто бомбували німецькі літаки. 13 вересня, коли становище польських військ на цьому напрямі стало критичним через небезпеку оточення, тюремна адміністрація поквапно евакуювалася. Сидячи в одиночній камері, Бандера нічого не знав про події, що відбувалися в світі. Аж ось він почув якийсь незрозумілий гомін у коридорах, гуркіт дверей, нарешті двері його камери відчинилися: «Друже Степане, ви вільні!» Звільненню сприяли в’язні-націоналісти – якимсь чином вони дізналися, що їхній лідер сидить в одиночній камері.

Колишній в’язень із групою кількох звільнених із в’язниці українських націоналістів рушив із Бреста у напрямі Львова. Вони потай пробиралися путівцями, стараючись уникати зустрічей як із польськими, так і з німецькими військами. До того ж польські землі вже «звільняли» радянські війська, а від радянської влади Степан Бандера теж нічого хорошого не сподівався. У дорозі велику підтримку Бандері і його товаришам надавало українське населення. На Волині і, трохи пізніше, в Галичині Бандера зв’язався з діючою тоді мережею ОУН, яка почала створювати партизанські загони, піклуючись про охорону українського населення, готуючи зброю і боєприпаси для майбутньої боротьби. У невеликому місті Соколові відбулася зустріч з територіальними керівниками ОУН.

З ними крайовий провідник обговорив ситуацію і напрями подальшої роботи. Ставлення на той момент складалося таке: розвал Польщі був очевидним, і до того ж стало відомо, що більшовики мають зайняти більшу частину західноукраїнських земель відповідно до договору з гітлерівською Німеччиною. Тому вся діяльність ОУН на ЗУЗ повинна була швидко перебудуватися на боротьбу проти більшовиків. З Сокола Бандера разом із майбутнім членом Бюро Проводу ОУН Дмитром Маєвським вирушив у Львів, куди вони прибули за кілька днів після вступу до міста більшовицької армії.

У Львові Бандера пробув два тижні. Жив конспіративно, проте у зв’язку з безладдям вільно пересувався і увійшов у контакт не тільки з активом ОУН, але і з деякими керівними діячами українського церковного і національного руху. Офіційним крайовим провідником ОУН у Західній Україні тоді був В. Тимчій-Лопатинський, який цілком визнавав авторитет Бандери і поділяв його погляди. Разом із членами крайового керівництва й іншими членами ОУН, які в той час були у Львові, обговорювалися плани подальшої діяльності ОУН на українських землях і її антибільшовицької боротьби. На першому місці було створення мережі ОУН на всій території України, захопленої більшовиками, був також узгоджений план революційної боротьби на території України незалежно від ходу війни, продумувались дії на випадок масових репресій і депортацій радянською владою населення Західної України.

Переслідування націонал-патріотично настроєних представників інтелігенції не змусили себе довго чекати. Степан Бандера чудово усвідомлював те, що, залишаючись у Львові, він наражається на велику небезпеку, до того ж даремно марнує час. Він запропонував піти в ліси і виявив гаряче бажання залишитися в Україні, щоб безпосередньо брати участь у революційно-визвольній діяльності ОУН. Проте інші члени організації наполягали на тому, щоб Степан пішов за межі території більшовицької окупації і вже звідти вів організаційну роботу. Остаточно все вирішилося після приходу кур’єра від Проводу з-за кордону з таким самим проханням. У другій половині жовтня 1939 року Бандера покинув Львів і разом із братом Василем, який повернувся в місто з польського концтабору в Березі Картузькій, з чотирма іншими членами ОУН перейшов радянсько-німецьку демаркаційну лінію кружними шляхами, а потім прибув до Кракова.

Керівництво ОУН здогадувалося про майбутні репресії з боку Москви, і тому багато хто, не чекаючи приходу Червоної Армії, перебрався за кордон. Більшість із них поселилися біля Кракова і в самому Кракові. На той момент це польське місто стало центром українського політичного, культурно-просвітницького і суспільного життя на західних окраїнах українських земель під німецькою окупацією.

Після прибуття до Кракова Степан Бандера активно включився в діяльність ОУН. Він працював у місцевому центрі, в якому зібралося багато керівних діячів із ЗУЗ, польських в’язниць, було декілька ветеранів, які вже давно жили в Німеччині, Чехословаччині й Австрії. Спочатку становище Степана в організації фактично не було жодним чином визначено. Справді, колись він очолював крайову екзекутиву, але ж після цього був засуджений на довічне ув’язнення, а після нього цю посаду почергово вже посідало кілька людей.

У листопаді 1939 року Бандера змушений був виїхати на два тижні до Словаччини для лікування ревматизму, що посилився в сирих катівнях польських в’язниць. Разом із ним поїхали кілька звільнених українських політичних в’язнів, серед яких були видатні керівні члени ОУН, що працювали в ЗУЗ, Закарпатті і в еміграції. Це дало можливість провести в Словаччині декілька нарад керівного активу ОУН, на яких була проаналізована ситуація, що склалася, шляхи розвитку визвольної боротьби, внутрішні організаційні справи в країні і за кордоном.

Подальший шлях Бандери зі Словаччини лежав до Відня, де також знаходився потужний закордонний центр ОУН, в якому концентрувалися зв’язки ОУН із ЗУЗ в останні роки польської окупації, а також із Закарпатською Україною. У кінці 1939-го або в перші дні 1940 року до Відня приїхав Тимчій-Лопатинський. Було вирішено, що вони вдвох поїдуть до Італії на зустріч із лідером Проводу ОУН А. Мельником. Бандера мав намір обговорити з лідером організації низку справ, проектів внутрішньоорганізаційного і політичного характеру для налагодження ділових відносин між Проводом українських націоналістів і крайовим революційним активом. Після смерті Євгена Коновальця між крайовим Проводом і активом організації та центральним керівництвом склалися ненормальні стосунки. Причиною цього була, серед іншого, недовіра до деяких найближчих співробітників полковника А. Мельника, зокрема до Ярослава Барановського.

Крайова служба безпеки ОУН підозрювала, що Барановський пов’язаний із польською поліцією і винен у провалі крайового керівництва в 1934 році. Є відомості, згідно з якими під час побачення у в’язниці з братом Степан Бандера встиг йому сказати, що польська поліція знає про такі справи, які були відомі тільки двом людям в організації: самому Бандері і Ярославу Барановському. Оцього другого звинувачували також у тому, що саме він переконав Андрія Мельника прийняти на себе керівництво Проводом українських націоналістів, посилаючись на нібито усний заповіт Євгена Коновальця. При цьому молоді революціонери справедливо зауважували, мовляв, який може бути заповіт, та ще до того ж усний, людини, котрій було всього сорок сім років? До того ж в ОУН існувала виборна система. І після трагічної смерті всіма шановного Євгена Коновальця, на думку прихильників Бандери, мали відбутися вибори. Було висунуто вимогу усунути Барановського і провести щодо нього внутрішнє розслідування. Така ж вимога була висунута і щодо Зиновія Книша, одного з ветеранів, якого звинувачували в тому, що він є агентом НКВС.