Когда Феликсу оставалось совсем немного до восемнадцатилетия, он в марте 1914 года завершил учебу и смог осуществить свою давнюю мечту — поступить в прусскую армию кадетом. Однако получить военное образование в условиях мирного времени ему не пришлось. В августе 1914 года началась Первая мировая война, кадеты старшего возраста были срочно произведены в фенрихи (или в лейтенанты) и отправлены на фронт. Кадеты же младших возрастов также покинули казармы, получив права вольноопределяющихся (что давало возможность достаточно быстро получить офицерское звание, причем офицера действительной службы, а не офицера резерва). В числе последних оказался и молодой Феликс Штейнер. Он был зачислен в 5-ю роту 41-го Восточно-прусского пехотного фон Бойена полка. В составе 8-й армии молодой кадет отправился на войну с русскими. Он сразу же показал себя отличным, храбрым и инициативным солдатом, и свидетельством этому является полученный им уже 9 октября 1914 года Железный крест 2-го класса. 14 ноября 1914 года Штейнер был ранен (затем он с честью носил черный Знак за ранение) и отправлен в госпиталь. После выздоровления молодой и перспективный унтер-офицер был отправлен в Военную академию II армейского корпуса в Кёнигсберге. Академия фактически представляла собой ускоренные курсы младших офицеров для отличившихся вольноопределяющихся и унтер-офицеров. 27 января 1915 года Феликсу Штейнеру было присвоено первое офицерское звание лейтенанта, и он вернулся на Русский фронт, приняв участие в боях в Курляндии — через почти 30 лет он вновь будет вести здесь тяжелые бои.
В январе 1916 года Штейнера перевели в резервный батальон все того же 41-го полка, теперь его задачей была подготовка пополнения — учения, прививание новобранцам навыков ближнего боя и т. д. Именно здесь Штейнер начал вырабатывать свою методику подготовки личного состава, ставшую позже образцом для всех войск СС. В июне 1916 года он был направлен в 376-й пехотный полк, сражавшийся на Западе. Примерно в это время немецкое командование озаботилось вопросом создания ударных отрядов. Это стало отчаянной попыткой германского командования хоть как-то изменить ход позиционной войны. В эти отряды, которые обычно формировались на уровне корпуса, переводились из пехотных частей наиболее храбрые и физически сильные солдаты и офицеры. Они должны были играть роль ударной силы при осуществлении прорывов и проведении стремительных контратак на наиболее уязвимых участках. Личный состав штурмовых отрядов проходил специальную подготовку: солдат учили приемам рукопашного боя (в том числе и с использованием саперных лопаток), а также в совершенстве владеть такими видами вооружений, как пулеметы, гранаты, а также огнеметы. Кстати, именно у огнеметчиков (как, впрочем, и у танкистов) во время Первой мировой войны появилась эмблема рода войск — череп со скрещенными костями, примерно такой же, как стали позже носить СС. Ударные отряды официально именовались отрядами отличных стрелков (снайперов) — Scharfschützetruppen, что не совсем соответствовало их задачам, но в то же время подчеркивало высокий уровень подготовки личного состава. В числе других отличных строевых офицеров Штейнер был зачислен в эти формирования: сначала командиром пулеметной роты 97-го ударного отряда, а в октябре 1916 года переведен на такой же пост в 46-й ударный отряд. Штейнер принял участие в многочисленных атаках на Западном фронте, и, несмотря на большой накал боев, судьба его берегла — больше ранений в Первую мировую войну он не получил. Отличия в боях с англичанами и французами принесли ему 3 ноября 1917 года Железный крест 1-го класса, а в последние дни войны — 18 октября 1918 года — звание обер-лейтенанта.
После окончания войны Штейнер сначала, в ноябре 1918 года, был назначен командиром 3-й запасной пулеметной роты XVII армейского корпуса, а в первых числах января 1919 года отправился на родину. Как и многие ветераны, он вступил в ряды Добровольческого корпуса — это были нерегулярные вооруженные формирования, члены которых подчинялись воинской дисциплине и под руководством своих командиров вели вооруженную борьбу против деструктивных сил: прежде всего коммунистических отрядов, а на окраинах Германии — против представителей национальных меньшинств, которые после крушения Германской империи стали предпринимать активные попытки по отторжению от страны ряда ее территорий в пользу возникших на ее обломках национальных государств. В рядах Добровольческого корпуса Штейнер принял участие в операциях в районе Мемеля (ныне Клайпеда). Отстоять немецким националистам Мемель не удалось, и этот город по условиям Версальского мира был передан в ведение держав-победительниц, а в февраля 1923 года присоединен к Литве.
В это время Добровольческие корпуса и отряды местной самообороны составляли так называемый черный рейхсвер — то есть как бы нерегулярные военизированные отряды, выпадавшие из-под действия Версальского мира, а на самом деле обычные воинские формирования, тайно финансировавшиеся правительством. Постепенно под давлением держав-победительниц черный рейхсвер начал сворачиваться, и 8 мая 1920 года Штейнер был официально зачислен на службу в рейхсвер и назначен командиром 2-й (пулеметной) роты 2-го стрелкового полка. Как и все офицеры рейхсвера, при зачислении на службу Штейнер подписал контракт на 25 лет службы. 1 октября 1920 года Штейнер был назначен командиром 8-й (пулеметной) роты 1-го пехотного полка в столице Восточной Пруссии, городе Кёнигсберге (ныне Калининград, центр Калининградской области Российской Федерации), а в сентябре 1923 года зачислен в штаб полка в качестве офицера пулеметного дела — в его обязанности входила организация подготовки личного состава. Карьерный рост в рейхсвере был очень медленным; несмотря на то что Штейнер был хорошим строевым офицером, звание капитана он получил только 1 декабря 1927 года, в октябре 1929 года назначен адъютантом 1-го пехотного полка.
Основываясь на своем военном опыте, Штейнер разработал концепцию развития вооруженных сил будущего: главным положением ее являлось то, что в характер войны будущего будет кардинально отличаться от того, что имело место в Первой мировой войне. Это будет мобильная и скоротечная война, где все будут решать техническое обеспечение, уровень вооружений, а также профессиональное мастерство солдат. Таким образом ведущую роль в будущей войне, по мнению Штейнера, будут играть не многомиллионные армии, сформированные на основе всеобщей воинской повинности, а небольшие мобильные, хорошо вооруженные и специально подготовленные ударные части. В их задачу, по мнению Штейнера, входило стремительными ударами прорывать оборону противника, осуществлять окружение, а затем и уничтожать окруженные части. Эти части должны были быть высокомобильными и вооружены новейшими видами вооружения — автоматическим оружием. (В скобках заметим, что Штейнер несколько опередил свое время: подобная концепция больше применима в военно-политической ситуации конца XX — начала XXI века, чем к периоду Второй мировой войны. Сегодня подход Штейнера успешно применяется в армиях крупнейших мировых держав и дает им возможность малыми силами проводить очень эффективные военные операции. Наша страна, к сожалению, является исключением.) Новаторские идеи Штейнера не нашли ни понимания, ни поддержки у руководства рейхсвера. Возглавлявшие рейхсвер (а затем и вермахт) генералы, в большинстве своем прошедшие Первую мировую войну в штабах, отдавали предпочтение именно массовой армии, именно всеобщая воинская повинность стала основополагающим принципом официальной доктрины рейхсвера (вермахта).
После прихода нацистов к власти большинству офицеров стало ясно, что в армии грядут кардинальные перемены. И они, естественно, приветствовали политику новой радикальной партии и стали ждать скорых изменений. Но генералы не торопились, у них было свое видение развития вооруженных сил Германии. Кроме того, какая-либо политическая (пусть и националистическая) активность в рейхсвере не приветствовалась и не слишком уживчивый и радикальный Штейнер оказался не ко двору. В октябре 1933 года его перевели на должность офицера для особых поручений, а в декабре того жде года он вообще оставил военную службу и перевелся в прусскую земельную полицию, которую контролировал сам Герман Геринг. Правда, перевод в полицию дал и определенный карьерный рост — он получил звание майора.
