По возвращении в 1783 году, Гнейзенау несколько лет служит в Байрейте, в пехотном полку, и завоевывает себе в небольшом городке всеобщие симпатии. По свидетельству Александра Гумбольдта, посетившего Байрейт в 1796 году, местные жители еще через десять лет после отъезда Гнейзенау с интересом вспоминали о нем.
Но служба в маленьком гарнизоне не удовлетворяет Гнейзенау, несравненно более образованного, чем его товарищи; он изучает науки, требующиеся для военного инженера и офицера генерального штаба, и обращается к Фридриху II, приступившему к формированию королевской свиты по генерал-квартирмейстерской части, с предложением своих услуг. Фридрих II соглашается и предлагает ему явиться в Берлин. Но Гнейзенау, уволившийся из анспахских войск, не понравился Фридриху II при личном представлении; Фридрих II обладал удивительной способностью браковать каждого сколько-нибудь талантливого человека. Прусский король обманул Гнейзенау и принял его в прусскую армию, но не в генеральный штаб, а младшим офицером в пехотный полк, расположенный в глухом силезском гарнизоне.
С 1786 года Гнейзенау на 20 лет погряз в скромном существовании маленького гарнизона. В Силезии Гнейзенау женился — так же молниеносно, как делал все в жизни. Его приятель, жених «хорошенькой Котвиц», бойкой помещичьей дочки, был убит на дуэли, и на Гнейзенау, бывшего секундантом, выпал тяжелый долг сообщить невесте это горестное известие. «Хорошенькая Котвиц» пришла в такое отчаяние, что Гнейзенау почувствовал необходимость утешить ее и, не зная ни в чем предела, тут же предложил ей свою руку и сердце.
К моменту катастрофы прусского государства 46-летний Гнейзенау дослужился уже до чина капитана, командовал батальоном, имел пятерых детей и ожидал рождения шестого, читал агрономические труды и деятельно управлял небольшим имением жены.
С этого времени начинается резкий сдвиг в развитии Гнейзенау. Суждения его в начале кампании 1806 года, в противоположность высказываниям Клаузевица, отличались большой зрелостью. Летом 1806 года он записал: «У нас господствует большое недовольство миром. Справедливо ли? Это большой вопрос. Кто бы мог сказать, какой ход приняли бы события при противоположной политике?» Мобилизация вызвала у него замечание: «поздно, быть может не слишком поздно». Перед самой катастрофой он писал: «Со стороны я вздыхаю. Много времени упущено, занимались мелочами, давали представления публике, а весьма серьезное дело — подготовку к войне— забыли. Дух офицеров превосходен, на этом можно строить большие надежды, но… Что будут делать французы дальше, я знаю. Но что я буду сам делать, мне неизвестно. Я отчетливо представляю наступление французов вдоль реки Заалы. Но я сижу в низших чинах, и мое слово не имеет цены. У меня щемит сердце, когда я представляю себе последствия. Отечество, избранное мною отечество! Я забыт в своем маленьком гарнизоне и лично могу только драться, но не советовать».
Гнейзенау участвовал в первом же бою этой кампании, под Заальфельдом. При отступлении, прикрывая батарею, батальон Гнейзенау сражался не по уставу — не в сомкнутом развернутом строю, а по-новому — весь рассыпанный в цепь против французских стрелков. Это свидетельствует, что поездка Гнейзенау в Америку не пропала даром, и он не только усвоил американские передовые взгляды на тактику пехотного боя, но и соответственно подготовил свой батальон, забежав совершенно самостоятельно далеко вперед устава.
В бою под Заальфельдом Гнейзенау был ранен и должен был сдать командование батальоном. Уехать для лечения в тыл ему не удалось — катастрофа застигла его раньше. Раненый Гнейзенау в день сражения под Йеной и при отступлении выполняет обязанности офицера генерального штаба при штабе армии.
В конечном счете посланный для связи из одной колонны в другую, он прибывает в то время, когда эта колонна уже сдалась французам. Возвращается обратно — там армия тоже сдается. Гнейзенау остается одиноким и без средств на территории, занятой французами. А вдали, в Восточной Пруссии, сопротивление при помощи союзников — русских войск — продолжается. Гнейзенау пытается пробраться в Кенигсберг через шведскую Померанию, но шведская пограничная охрана имеет приказание никого не пропускать. Узнав, что шведские пограничники арестовывают французских шпионов, Гнейзенау прибегает к последнему средству: он подходит к шведским пограничникам и так искусно выполняет роль французского шпиона, что шведы немедленно арестовывают его и доставляют своему высшему командованию. На допросе у шведского генерала Гнейзенау сознается, что сознательно обманул пограничников, и шведы дают ему возможность морем пробраться в Кенигсберг.
В Кенигсберге подвиги и приключения Гнейзенау были награждены чином майора, но он не понравился прусскому королю. В небольшом корпусе, уцелевшем из всей прусской армии, все вакансии оказались занятыми, и Гнейзенау был назначен командовать запасным батальоном. Его просьба — дать возможность сформировать партизанский отряд — была отклонена. Но судьба, систематически мешавшая Клаузевицу выделиться, избрала Гнейзенау своим баловнем.
Наиболее патриотичной в Пруссии была буржуазия небольшого города — крепости Кольберга, многократно выдержавшего в XVIII веке осаду шведов и русских. Сдача шести больших прусских крепостей их комендантами заставила вождей кольбергской буржуазии проявлять особую бдительность по отношению к своему коменданту, старому полковнику фон-Лукаду, не пользовавшемуся доверием. Когда же у коменданта крепости произошло столкновение с капитаном Шилем, организовавшим из Кодьберга партизанские действия на тылах французов, и комендант приказал арестовать Шиля, по городу разнеслась весть о том, что комендант подготовляет измену: начался бунт. Депутация горожан требовала у прусского короля дать им другого, надежного коменданта. Необходимость удовлетворить строптивых буржуа заставила короля обсудить этот вопрос со своими министрами. Бейме, один из влиятельных гражданских статс-секретарей, заявил, что встретил только что на лестнице незнакомого майора, который ему кажется очень подходящим для горячего поста коменданта Кольберга. Так состоялось назначение Гнейзенау.