1 января 1934 года Штейнер вступил в СА (с чином штурмфюрера) и НСДАП, получив билет № 4 264 195, одновременно он был привлечен к руководству службой боевой подготовки в СА. Однако вольница Штурмовых отрядов не устраивала боевого офицера, тем более сторонника теории ударных войск. Поэтому не было ничего странного, что в 1935 году, когда начали формироваться части усиления СС, он был привлечен в их состав Паулем Хауссером. 24 апреля 1935 года Штейнер стал членом СС, получив SS-Nr. 253 351, и ему было присвоено звание оберштурмбаннфюрера СС, что было выше его предыдущего звания и соответствовало званию майора рейхсвера. Хауссер сразу же назначил Штейнера командиром 3-го штурмбанна 1-го штандарта СС (позже — штандарт СС «Дойчланд»).

В частях усиления СС Штейнер работал вместе с бароном Кассиусом фон Монтиньи — о нем сегодня практически никто не помнит, а его вклад в дело формирования войск СС был не меньше, чем Штейнера, с которым он работал в постоянной связке. Монтиньи родился 29 октября 1890 года в Дюссельдорфе и с 1909 года служил в военно-морском флоте, причем в 1912 году — на подводных лодках. В мае 1915 года он был произведен в обер-лейтенанты и затем командовал подводными лодками UB-38, UB-30, UB-10 на Балтийском и Северном морях. Как и Штейнер, он был награжден Железным крестом 1-го и 2-го класса. После окончания войны в декабре 1918 — ноябре 1919 года Монтиньи командовал отрядом бронеавтомобилей в штурмовом батальоне 3-й морской бригады Лёвенфельда — одного из подразделений Добровольческого корпуса, — в составе которой участвовал в боях против поляков в Нижней Силезии, а затем против коммунистов в Руре. В 1920 году барон принял участие в Капповском путче. В 1920-1934 годах Кассиус фон Монтиньи служил в полиции и дослужился до звания полковника. Осенью 1934 года, при расширении вооруженных сил, он смог вновь поступить на военную службу и был назначен командиром пехотного полка. В апреле 1937 года он оставил службу в армии — прежде всего потому, что вермахт не соответствовал его воззрениям на формирование элитных ударных соединений, а взял курс на создание массовой армии. Применение своим способностям и реализацию своих планов Монтиньи смог осуществить в СС, куда он вступил 1 апреля 1938 года.

Штейнер и присоединившийся к нему позже Монтиньи разработали систему подготовки личного состава войск СС по образцу штурмовых частей кайзеровской армии. Приняв командование, Штейнер немедленно приступил к осуществлению своей программы: минимум шагистики, максимум спорта и военной подготовки. Обычным делом стали марш-броски с полной выкладкой; и здесь Штейнер добился высоких результатов: современники указывали, что на учениях его подчиненные показали невероятный результат — с оружием в руках, с противогазами и ранцами они преодолели дистанцию в три километра за 20 минут!

Другим новшеством Штейнера, которое прижилось в войсках СС и стало их визитной карточкой, было микширование различий между солдатами, унтер-офицерами и офицерами, естественно, при сохранении железной дисциплины. Именно в войсках СС младшие чины обращались к старшим только по званию, не добавляя, как в армии, слово «господин» (Herr). Подобные методы дали прекрасный результат — первые дивизии СС отличались спаянностью и представляли собой единое «фронтовое братство». В составе батальона верный своим принципам Штейнер начал формирование ударных групп, личный состав которых должен был вооружаться автоматическим оружием (пистолетами-пулеметами), ручными гранатами. Штейнеру же соединения СС обязаны и своим прозвищем «древесные лягушки». Так их стали называть за пестрые камуфляжные костюмы, которых в вермахте не было. Инициатором их введения в частях СС выступил именно Штейнер.

Хотя методика Штейнера и не очень устраивала Хауссера, для которого она была слишком революционной, не оценить рвения и талантов своего подчиненного он не мог. Кроме того, прекрасные и быстрые результаты вызвали шумное одобрение рейхсфюрера СС. В результате уже 1 июня 1936 года Феликс Штейнер был произведен в штандартенфюреры СС и назначен командиром штандарта СС «Дойчланд» (Deutschland), дислоцированного в столице Баварии — Мюнхене. Этот штандарт был сформирован в 1934 году из политического резерва «Вюртемберг», политического резерва «Мюнхен» и австрийских добровольцев «Хильфсверк-Шлейссхейм» (Hilfswerk Schleissheim). Первоначально он получил название 2-го штандарта СС частей усиления СС (SS-Standarte 2/VT), а после того, как «Лейбштандарт СС Адольф Гитлер» получил статус самостоятельной части, стал именоваться 1-м штандартом СС. Во время торжеств по случаю партийного съезда в Нюрнберге в ноябре 1935 года этот штандарт первым в СС (не считая, естественно, «Лейбштандарта») получил почетное наименование — «Дойчланд».

К марту 1936 года подразделения штандарта дислоцировались: 1-й штурмбанн в Мюнхене, 2-й — в Дахау, 3-й — в Эллвангене (Вюртемберг). Стараниями Штейнера численность штандарта постоянно росла: 2580 человек в январе 1936 года, 2951 человек в январе 1937 года и 3186 в январе 1938 года. Однако затем, к декабрю 1938 года, его численность снизилась до 2850 человек — часть кадров штандарта была выделена на формирование нового штандарта частей усиления СС «Фюрер».

Штандарт «Дойчланд» — лучший в частях усиления СС — принял участие во всех «цветочных войнах»: в аншлюсе Австрии, занятии Судетской области и оккупации Чехии. Штейнер, как и все участники этих операций, получил Медаль в память 13 марта 1938 год и Медаль в память 1 октября 1938 года и позже к ней шпангу «Пражский град». Не обошлось дело без различных трений с рейхсфюрером СС и высшим руководством СС. Камнем преткновения стало желание пришедших в части усиления СС кадровых офицеров (таких как Хауссер, Штейнер, Гилле и другие) дистанцироваться от СС как политической организации и фактически превратить эти части в элитные подразделения вермахта, обладающие определенной самостоятельностью и находящиеся в привилегированном положении. Это в свою очередь не устраивало рейхсфюрера, стремившегося к созданию армии, которая выражала бы «единство испытанных членов партии с носителями оружия в ее рядах». И соответственно командиры войск СС оставались чужими для партийной верхушки Охранных отрядов. Например, Гейнц Хёне приводит следующую характеристику Штейнера, данную ему штандартенфюрером Эрнстом Фиком, являвшимся инспектором мировоззренческого воспитания в Главном управлении СС: он человек «духовно близкий вермахту, плюсом которого являются военные традиции, минусом же — тугодумие в понимании наших политических проблем».

Постепенно изменялась и уточнялась структура штандарта, и к началу Второй мировой войны — 1 сентября 1939 года — он принял следующий вид:

Как наиболее боеспособное соединение частей усиления СС полк «Дойчланд» (вместе с артиллерийским полком СС) был включен в состав действовавшей в первом эшелоне группы «Кемпф», входившей в состав I армейского корпуса 3-й армии генерала артиллерии Георга фон Кюхлера. Перед началом кампании группа размещалась в Ниденбурге (Восточная Пруссия).

Эсэсовцы Штейнера отличились в боях на Млавском направлении. После перехода границы «Дойчланд» получил приказ прорвать оборону противника. Штейнер принял решение о лобовой атаке, но недооценил польских противотанковых заграждений, и полк попал под сильный артиллерийский огонь и понес значительные потери. Однако и в этой ситуации (а также при отсутствии поддержки с воздуха) Штейнер продолжил атаку, и к моменту остановки наступления эсэсовцы были в 100 метрах от польской линии обороны. На следующий день полк был переброшен к Хорцелю, где оборона поляков была прорвана, и он начал наступление на Розан.