Решив вопрос с начальником штаба, генеральный штаб стал подыскивать командующего армией. Людендорф, как все признавали, был человеком незаурядных способностей, но чтобы «комплект» был полным, нужен был настоящий «фон». Перебрали имена всех отставных командиров корпуса, и тут фон Штейн вспомнил, что накануне войны он получил письмо от бывшего товарища, сообщавшее: «Не забудь меня, если окажется, что где-то нужен командир», – и что его автор «ещё крепок». Именно тот, кто нужен. Гинденбург происходил из старой юнкерской семьи, жившей в Пруссии столетия. Служил в генеральном штабе у Шлиффена, прошёл все ступени до начальника штаба корпуса, а потом стал и его командиром; в отставку ушёл в 1911 году в возрасте шестидесяти пяти лет. Через два месяца ему исполнится шестьдесят восемь, но он был не старше Клука, Бюлова и Хаузена, трёх генералов правого крыла. Теперь на востоке, после паники Притвица, был нужен человек без нервов, а Гинденбург в течение всей своей безупречной карьеры был известен абсолютной невозмутимостью. Мольтке одобрил его кандидатуру, кайзер дал своё согласие. Отставному генералу была направлена телеграмма.
Гинденбург был у себя дома в Ганновере, когда в 3 часа дня пришла телеграмма с вопросом, примет ли он «немедленное назначение». Он ответил: «Я готов». Вторая телеграмма предписывала ему немедленно выехать на восток и принять командование 8‑й армией. Генеральный штаб даже не приглашал его в Кобленц для беседы. В телеграмме указывалось, что он должен сесть на поезд в Ганновере, и сообщалось, что его начальником штаба будет генерал Людендорф, который встретится с ним в том же поезде. У Гинденбурга едва хватило времени на то, чтобы перед отъездом заказать новую полевую форму серо-стального цвета, и к месту службы он, к своему большому смущению, отправился в старом синем мундире прусского генерала.
Когда через несколько дней о снятии Притвица стало известно, княгиня Блюхер в своём бесценном для историка дневнике записала: «Его место занял некий генерал Гинденбург, человек весьма преклонного возраста». Газетчики поспешно разыскивали сведения о новом командующем, что было довольно трудно сделать, поскольку в списках военных он числился как Бенекендорф. Они с удовольствием обнаружили, что он сражался под Седаном и заслужил Железный крест второй степени, а также был ветераном более ранней кампании 1866 года против Австрии. Его предки, Бенекендорфы, были среди тевтонских рыцарей, осевших в Восточной Пруссии, а имя Гинденбург было добавлено в восемнадцатом веке в результате женитьбы кого-то из прадедов. Он родился в городе Позен, в Восточной Пруссии, и в начале своей карьеры, будучи офицером штаба I корпуса, стоявшего под Кёнигсбергом, изучал проблему влияния Мазурских озёр на возможные военные действия. Из этого факта вскоре выросла легенда о том, будто бы Гинденбург спланировал сражение под Танненбергом ещё тридцать лет назад. Вырос он в имении своего деда в Нойдеке в Западной Пруссии, где, как он вспоминал, мальчиком любил разговаривать со старым садовником, который когда-то две недели проработал у Фридриха Великого.
Гинденбург уже ждал на перроне в Ганновере, когда в 4 часа утра подошёл поезд. Генерал Людендорф, которого он до этого никогда не видел, «энергично вышел» из вагона для доклада. Пока они ехали на восток, он подробно рассказал новому командующему о сложившейся ситуации и о тех распоряжениях, которые уже отдал. Гинденбург выслушал и одобрил. Так, по пути к сражению, сделавшему их знаменитыми, родился союз, который изображался мистической монограммой HL и которому суждено было править имперской Германией до самого её конца. Когда позднее Гинденбург стал фельдмаршалом, он получил прозвище «Маршал Что-ты-скажешь» – из-за привычки вместо ответа на заданный вопрос поворачиваться к Людендорфу со словами: «Was sagst du?» («Что ты скажешь?»)
Характерно, что первым лицом, которого генеральный штаб проинформировал об изменениях в командовании 8‑й армии, был начальник железных дорог Восточного фронта генерал-майор Керстен. Днём 22 августа, ещё до того как специальный поезд отправился в путь, он вошёл к Гофману «с крайне озадаченным лицом» и показал ему телеграмму, извещавшую, что на следующий день в Мариенбург прибудет дополнительный поезд, который доставит нового командующего и нового начальника штаба. Именно так Притвиц и Вальдерзе узнали о своём смещении. Часом позднее Притвиц получил личную телеграмму, сообщавшую, что он и Вальдерзе переведены в «список откомандированных». «Он уехал от нас, – вспоминает Гофман, – без единого слова сожаления по поводу того, как с ним поступили».