В конечном счете посланный для связи из одной колонны в другую, он прибывает в то время, когда эта колонна уже сдалась французам. Возвращается обратно — там армия тоже сдается. Гнейзенау остается одиноким и без средств на территории, занятой французами. А вдали, в Восточной Пруссии, сопротивление при помощи союзников — русских войск — продолжается. Гнейзенау пытается пробраться в Кенигсберг через шведскую Померанию, но шведская пограничная охрана имеет приказание никого не пропускать. Узнав, что шведские пограничники арестовывают французских шпионов, Гнейзенау прибегает к последнему средству: он подходит к шведским пограничникам и так искусно выполняет роль французского шпиона, что шведы немедленно арестовывают его и доставляют своему высшему командованию. На допросе у шведского генерала Гнейзенау сознается, что сознательно обманул пограничников, и шведы дают ему возможность морем пробраться в Кенигсберг.
В Кенигсберге подвиги и приключения Гнейзенау были награждены чином майора, но он не понравился прусскому королю. В небольшом корпусе, уцелевшем из всей прусской армии, все вакансии оказались занятыми, и Гнейзенау был назначен командовать запасным батальоном. Его просьба — дать возможность сформировать партизанский отряд — была отклонена. Но судьба, систематически мешавшая Клаузевицу выделиться, избрала Гнейзенау своим баловнем.
Наиболее патриотичной в Пруссии была буржуазия небольшого города — крепости Кольберга, многократно выдержавшего в XVIII веке осаду шведов и русских. Сдача шести больших прусских крепостей их комендантами заставила вождей кольбергской буржуазии проявлять особую бдительность по отношению к своему коменданту, старому полковнику фон-Лукаду, не пользовавшемуся доверием. Когда же у коменданта крепости произошло столкновение с капитаном Шилем, организовавшим из Кодьберга партизанские действия на тылах французов, и комендант приказал арестовать Шиля, по городу разнеслась весть о том, что комендант подготовляет измену: начался бунт. Депутация горожан требовала у прусского короля дать им другого, надежного коменданта. Необходимость удовлетворить строптивых буржуа заставила короля обсудить этот вопрос со своими министрами. Бейме, один из влиятельных гражданских статс-секретарей, заявил, что встретил только что на лестнице незнакомого майора, который ему кажется очень подходящим для горячего поста коменданта Кольберга. Так состоялось назначение Гнейзенау.
Пробравшись 26 апреля 1807 года с моря в осажденную крепость, Гнейзенау вскоре сделался кумиром местных патриотов. Наполеон выделил для осады крепости корпус Мортье из итальянских и южно-германских контингентов, представлявших войска второго разбора. Гнейзенау, располагая довольно многочисленным гарнизоном, вел упорную оборону на далеко вынесенных передовых укреплениях Волчьей горы. В первом же приказе Гнейзенау, отданном для контратаки на занятую французами Волчью гору, чувствуется прирожденный командир и вождь. Последние слова гласили: «Я сам позабочусь о доставке гренадерам завтрака на укрепления Волчьей горы».
Несмотря на то, что силы Мортье и его осадная артиллерия все увеличивались, Гнейзенау бодро защищал крепость. 23 июня Мортье наметил новый штурм и приступил к нему, хотя до него уже дошло известие о заключении Тильзитского мира. Когда выяснился неуспех и этого последнего штурма, на французских батареях взвились белые флаги, и военные действия были прекращены.
На фоне печальных катастроф 1806–1807 годов блестящая защита Кольберга представляла единственное светлое пятно, и Гнейзенау сразу стал национальным героем. Он был включен в комиссию по реорганизации армии под председательством Шарнгорста, и как только Клаузевиц прибыл в Кенигсберг, быстро сблизился с ним. Гнейзенау был на двадцать лет старше Клаузевица, но сразу оценил его превосходство в смысле глубины и ясности мысли. Их связывало глубокое взаимное уважение, а противоположность характеров только сильнее скрепляла их дружбу.
Гнейзенау являлся тем членом кружка, на которого возлагалась задача — убедить короля взять враждебную Франции линию поведения. В конце 1808 года Гнейзенау подал королю записку, в которой излагал, что перед королем стоит альтернатива — или полное подчинение Наполеону, или вооруженная борьба с ним. Клаузевиц доказывал Гнейзенау, что такое объективное изложение, передающее решение на усмотрение короля, является политической и психологической ошибкой; следовало, напротив, сосредоточить все усилия на доказательстве того, что никакого выбора у короля нет, а существует один путь — сопротивление до последней крайности. «Я хочу, — писал Клаузевиц, — чтобы вы выступали как неумолимый пророк, как непроницаемый сын рока, с которым не уславливаются и не торгуются». Предложения Гнейзенау в конечном счете провалились не из-за «подхода», а из-за страха короля перед народной войной, развертывания которой добивался Гнейзенау.