При проезде через Вюрцбург Нейтхардт воспламенил сердце молоденькой девушки. Состоятельные родители, к тому же ярые католики, не хотели слышать о браке их дочери с каким-то проходимцем, бедняком и к тому же лютеранином. Девушка бежала от родителей и, не имея другого пристанища, следовала в повозке за артиллерийской частью, в которой служил муж. В этой повозке, за два дня до сражения под Торгау, в 1760 году родился наш герой. Охватывающий маневр Фридриха II вынудил обозы к быстрому ночному отступлению. Повозка молодой матери сломалась. Страдая от лихорадки, с ребенком на руках, она пересела на облучок военного фургона, бросив свой жалкий скарб. Ночью она уронила ребенка на дорогу, а к утру скончалась. Новорожденного подобрал обозный солдат. Отец, не найдя в обозе жены, отдал грудного младенца на воспитание в первую попавшуюся крестьянскую семью и забыл его на долгие годы.
Гнейзенау, вспоминая свое детство, говорил, что голода он не знал – у него всегда был кусок черного хлеба, но ноги его не имели никогда обуви. Главное его занятие было пасти гусей. Прошло около десяти лет, когда его разыскали и взяли к себе на воспитание дедушка и бабушка с материнской стороны. Внезапно он был перенесен в состоятельную буржуазную обстановку. Его воспитывали в иезуитской школе в Вюрцбурге, постоянно упрекая в том, что он крещен по лютеранскому обряду. До конца своей жизни Гнейзенау затруднялся определить, католик он или протестант, что нисколько не смущало его равнодушия.
От бабушки ему досталось небольшое наследство, которое он пропустил в один веселый год, поступив в Эрфуртский университет. Веселый, находчивый, красивый, очень красноречивый, Гнейзенау всегда и у всех пользовался успехом. Девушки отравлялись из-за Гнейзенау, мужчины дрались с ним на поединках: у Гнейзенау насчитывается в жизни до семи дуэлей, не считая полусерьезных студенческих. Деньги быстро таяли. Уже после одного года студенчества Гнейзенау был вынужден искать себе профессию.
В 19 лет он поступил в австрийский гусарский полк «кадетом», как называли в Австрии юнкеров, рассчитывая быстро сделать карьеру, так как Австрия находилась тогда в войне с Пруссией за баварское наследство. Но война закончилась почти тотчас же после поступления Гнейзенау на службу. Находясь в отпуске, Гнейзенау участвует в дуэли с печальным исходом, за которую ему могло достаться от военного начальства. Тогда, не соблюдая всех положенных формальностей, Гнейзенау раскланивается с австрийской армией и предлагает свои услуги, уже в качестве знакомого с военным делом молодого офицера, маркграфу Ансбах-Байрейтскому, одному из тех мелких немецких князьков, которым война Соединенных Штатов за независимость открыла новые источники дохода – поставку пушечного мяса Англии.
Гнейзенау принят на службу в егерский батальон и работает над своим военным образованием. Мы можем заключить о том, что он не был обыкновенным беспутным малым и что у него были более широкие интересы, по его сохранившемуся неплохому стихотворению 1781 года «На смерть Лессинга». Очередь отправления в Америку доходит до него только в 1782 году, к самому шапочному разбору; сражаться ему уже не пришлось, так как понесенные английской армией неудачи заставили Англию признать независимость Соединенных Штатов.
По возвращении в 1783 году Гнейзенау несколько лет служит в Байрейте, в пехотном полку, и завоевывает себе в небольшом городке всеобщие симпатии. По свидетельству Александра Гумбольдта, посетившего Байрейт в 1796 году, местные жители еще через десять лет после отъезда Гнейзенау с интересом вспоминали о нем.
Но служба в маленьком гарнизоне не удовлетворяет Гнейзенау, несравненно более образованного, чем его товарищи; он изучает науки, требующиеся для военного инженера и офицера Генерального штаба, и обращается к Фридриху II, приступившему к формированию королевской свиты по генерал-квартирмейстерской части, с предложением своих услуг. Фридрих II соглашается и предлагает ему явиться в Берлин. Но Гнейзенау, уволившийся из ансбахских войск, не понравился Фридриху II при личном представлении; Фридрих II обладал удивительной способностью браковать каждого сколько-нибудь талантливого человека. Прусский король обманул Гнейзенау и принял его в прусскую армию, но не в Генеральный штаб, а младшим офицером в пехотный полк, расположенный в глухом силезском гарнизоне.
С 1786 года Гнейзенау на 20 лет погряз в скромном существовании маленького гарнизона. В Силезии Гнейзенау женился – так же молниеносно, как делал все в жизни. Его приятель, жених «хорошенькой Котвиц», бойкой помещичьей дочки, был убит на дуэли, и на Гнейзенау, бывшего секундантом, выпал тяжелый долг сообщить невесте это горестное известие. «Хорошенькая Котвиц» пришла в такое отчаяние, что Гнейзенау почувствовал необходимость утешить ее и, не зная ни в чем предела, тут же предложил ей свою руку и сердце.