Одним из наиболее известных информаторов польской контрразведки в ОУН был бывший боевик организации Роман Барановский, брат члена Провода ОУН Ярослава Барановского, который три года работал на дефензиву. Он был завербован поляками ещё в конце 1920-х гг. и выдал многих руководящих деятелей ОУН, в т. ч. краевого проводника Ю. Головинского, убитого в тюрьме.
Активизация польских спецслужб требовала принятия мер по защите подполья. Первое специальное контрразведывательное подразделение — «контрольно-разведывательная референтура» в ОУН — было создано в 1932 г. на Пражской конференции. Его возглавил студент-медик Я. Макарушка. Одной из важнейших функций этого подразделения был сбор информации о тайном сотрудничестве украинцев с польской полицией. С 1930 по 1939 год СБ ОУН было раскрыто и уничтожено более десяти польских агентов-провокаторов. В феврале 1939 г. сеть ОУН на ЗУЗ возглавил М. Тураш («Грабовский»). В созданной им Краевой экзекутиве ОУН в регионе (КЭ ОУН на ЗУЗ), была создана референтура Службы безопасности, которую возглавил Богдан Рыбчук. Каждый член ОУН был обязан докладывать референту безопасности обо всех подозрительных проявлених.
После официального раскола ОУН 10 февраля 1940 г. на «мельниковцев» и «бандеровцев» большая часть сотрудников референтуры Службы безопасности поддержала Степана Бандеру. Службу безопасности возглавил заместитель Бандеры Николай Лебедь, а его заместителем М. Арсенич.
С марта 1941 г. и до своей гибели 23 января 1947 г. Службу безопасности возглавлял Микола Арсенич, под руководством которого она превратилась в эффективную карательную организацию.
В число руководителей высших уровней СБ в разное время входили Василь Турковский («Павло»), Василь Макар («Буженко»), Григорий Пришляк («Микушка», «Вайс», «Безродный»), Иван Клымив («Легенда»), Петро Козак («Смок»), Петро Федорив («Дальнич»), Мирон Каминский («Дон»), Петро Ковальский («Юрко»), Иван Равлик, Иван Кашуба, Евгений Врецена, Степан Мудрик.
Высокая эффективность СБ определялась несколькими факторами. Многие руководители службы имели многолетний опыт подпольной борьбы в условиях строжайшей конспирации. Известны случаи, когда руководители СБ ОУН давали своим сотрудникам задания вербоваться в школы абвера. Получив необходимые знания, эти сотрудники после получения первого задания немцев возвращались и работали в Службе безопасности. Повышению эффективности СБ способствовало также то, что в ходе отступления Красной армии летом 1941 г. в руки ОУН(б) попали оперативные документы из Управления НКВД в г. Луцке, где имелось подразделение заграничной разведки, а также архивы некоторых районных подразделений НКВД.
Руководители СБ регулярно проводили учебные сборы для повышения квалификации руководителей разного уровня. Особое внимание при этом уделялось изучению специальных дисциплин, таких как структура и методы работы спецслужб (царской охранки, НКВД, МГБ, «СМЕРШ», советской разведки, гестапо) и практическая деятельность СБ (вербовка информаторов, двойные агенты, ведение агентурных дел, следствие и допросы, разведка, отчёты, связь, конспирация). Изучались структура коммунистической партии, основы коммунистической идеологии, внутренняя и внешняя политика СССР и других стран. С руководителями районных, надрайонных и окружных референтур проводились занятия по истории соседних государств, общей психологии и психологии масс, логике и основам красноречия. Изучались методы дезинформации и провокаций, анализировались протоколы допросов разоблачённых агентов. В конце 1943 г. несколько учебных сборов для референтов СБ областного и районного уровней провёл руководитель СБ ОУН(б) Н. Арсенич.
Кадры для СБ готовила созданная ОУН совместно с немцами спецшкола в Кракове (Закопане, пансионат «Стамари»), законспирированная под курсы для подготовки спортсменов. Курсанты давали подписку о сотрудничестве с гестапо, и их планировалось использовать для развёртывания подрывной работы во время подготовки и ведения войны против СССР. Комплектованием сменного состава спецшколы занимался Н. Лебедь. Основными учебными дисциплинами были идеологическая подготовка (преподаватель Мирон-Орлик), организационная работа (Я. Старух), разведка и контрразведка (М. Арсенич), конспирация (Д. Маевский-Косарь).
До 1941 г., руководствуясь инструкциями ОУН, Служба безопасности должна была решать следующие задачи:
— бороться за здоровое моральное состояние в ОУН;
— противодействовать разведывательно-подрывной деятельности враждебных спецслужб и их агентуры;
— выполнять определённые функции судебной власти «в борьбе с вредителями и враждебными элементами для Украинского народа и Организации»;
— заботиться о личной безопасности членов ОУН и охране её имущества;
— создавать собственные позиции «на чужих и враждебных нам территориях с целью разведки, диверсии и провокации».
В апреле 1941 г. руководство ОУН(б) разработало для Краевого провода на ЗУЗ инструкцию «Борьба и деятельность ОУН во время войны», в которой определялись задачи СБ после начала войны Германии против СССР.
Информация о скором начале войны не была секретом для руководителей ОУН. В отчёте «О положении ОУН на Украине…» руководитель Краевого провода ОУН(б) на ЗУЗ И. Климов (Е. Легенда) 23 июля 1941 г. сообщал С. Бандере: «Известие о войне получил примерно 7 мая от вашего курьера, посланного ко мне, Тараса Онишкевича».
Инструкция призывала членов ОУН «немецкие войска принимать как войска союзников» и использовать их успехи для создания собственного государства, ведущей силой которого должна была стать сама ОУН — «орден борцов и фанатиков». Планировалось создание отделов «безопасности и информации» при всех территориальных органах ОУН.
На территории Польши началось формирование трёх «походных групп» ОУН(б) численностью от 1200 до 3–5 тыс. каждая. Группы должны продвигаться вслед за немецкими войсками, пропагандировать идею самостоятельности Украины и создавать гражданскую украинскую администрацию и полицию.
СБ обеспечивала секретность мероприятия. Были определены маршруты движения для каждой из групп: через Житомир на Харьков, через Винницу на Киев и через Днепропетровск на Одессу. На первом этапе СБ обеспечивала оперативное обеспечение продвижения походных групп ОУН походными референтурами. По мере формирования местной украинской администрации СБ должна была формировать стационарную сеть органов безопасности на Украине. Руководители походных рефентур должны были стать территориальными референтами СБ и подчиняться «Проводнику своей местности». В оперативных вопросах референтуры подчинялись только собственному руководству.
Считалось, что главной целью деятельности СБ станет «организация строя и порядка. Все акты правового государственного порядка могут обрести реальную силу, потому что есть орган, который сможет заставить непокорных признать их…»
В разделе инструкции «Общие направления политики ОУН на отдельных направлениях общественно-политической жизни» отмечалось, что СБ «имеет исполнительную силу государственными средствами уничтожать враждебные Украине элементы, которые станут на территории вредителями, а также имеет возможность контролировать общественно-политическую жизнь в целом».
В подразделе «Очищение территории от враждебного элемента» (п. 15) указывалось: «Во времена хаоса и смуты можно позволить себе ликвидацию нежелательных польских, московских и жидовских деятелей, особенно сторонников большевистско-московского империализма».
В подразделе «Политика в отношении национальных меньшинств» (п. 16) национальные меньшинства «делятся на: а) лояльные нам, собственно члены всё ещё угнетённых народов; б) враждебные нам — москали, поляки и жиды…Уничтожать в борьбе, в частности тех, которые будут защищать режим: переселять в их земли, уничтожать, главным образом интеллигенцию, которую нельзя допускать ни в какие руководящие органы, вообще сделать невозможным "производство" интеллигенции, доступ к школам и т. п. Руководителей уничтожать. Жидов изолировать, поубирать из управленческих структур, а также поляков и москалей. Если бы была непреодолимая нужда, оставить в хозяйственном аппарате жида, поставить ему нашего милиционера над головой и ликвидировать при наименьшей провинности. Руководителями могут быть только украинцы, а не чужаки-враги. Ассимиляция жидов исключается».
В разделе, посвящённому непосредственно СБ — «Инструкции службы безопасности», — «Народной милиции» указывалось: «…Существуют элементы… которые при создании нового революционного строя на Украине должны быть нейтрализованы. Этими элементами являются: русские, направленные на украинские земли для закрепления власти Москвы на Украине; евреи как индивидуально, так и как национальная группа; иноземцы, преимущественно разные азиаты, которыми колонизирует Москва Украину с целью создания на Украине национальной шахматной доски; поляки, на западноукраинских землях, которые не отреклись от мечты от построения Великой Польши, как раз за счёт украинских земель, хоть бы и Польша стала красной».
Перед «Народной милицией» ставилась задача «первоначального проведения чистки энкаведистов, русских, евреев и прочих», а также составления списков «отметившихся в преследовании и гонении украинцев — в первую очередь «неукраинцев», — а собственно, евреев, русских, поляков». В соответствии с инструкцией «Народная милиция» становилась единственным органом «государственной безопасности». В её структуре был создан «политический отдел, который назывался по аналогии с гестапо «Тайной государственной полицией (нем. Geheime Staatspolizei)».
Таким образом, к 1939–1941 гг. СБ была окончательно сформирована как организация. К этому времени было разработана структура управления, определены направления её деятельности и разработаны основные инструктивные документы. Служба безопасности развивалась и в период немецкой оккупации, однако её роль в ОУН особенно возросла с приходом на ЗУЗ Красной армии. Только после изменения тактики и при переходе подполья от выполнения военных операций к диверсионно-террористическим акциям СБ становится ведущим звеном ОУН(б).