Первые дни пребывания в Ставрополе были радостными от встречи с Натальей Михайловной и дочерью Елизаветой, но потом все чаще и чаще приходили тягостные мысли о будущей службе в Петербурге. Все петербургские друзья в один голос говорили в письмах, что он поторопился с рапортом генералу Гурко, надо было, дескать, сначала разузнать о возможностях службы в столице, а уж потом… Полковник Горемыкин перебрал все ведомства в поисках службы, наконец пошел к генералу Ивану Федоровичу Веймарну (1802–1846) и рассказал о сложностях и противоречиях бывшего его сослуживца Милютина, Веймарн со своими благосклонными предложениями обратился к начальнику штаба по военно-учебным заведениям, генералу от инфантерии Якову Ивановичу Ростовцеву (1803–1860), влиятельному другу Николая Первого, и тот тут же согласился предоставить место Милютину, как только освободится для него место профессора в Николаевской академии. Горемыкин на этом не остановился, пошел к новому генерал-квартирмейстеру Главного штаба Федору Федоровичу Бергу (1793–1874) и тоже изложил просьбу подполковника Милютина. Берг с готовностью принял эту просьбу и решил назначить его обер-квартирмейстером кавалерийского корпуса под командованием генерал-адъютанта Александра Львовича Потапова (1818–1886). Поступили из Петербурга и другие предложения, так что Дмитрий Алексеевич, ободренный такими предложениями, 3 сентября смело подал рапорт генералу Норденстаму «формальный рапорт о моем увольнении от должности, приложив медицинское свидетельство о расстроенном моем здоровье».
30 сентября представление пошло в штаб корпуса, 19 октября командующий корпусом направил военному министру Александру Ивановичу Чернышеву (1785–1857) представление о рапорте Милютина, Чернышев доложил об этом императору Николаю Первому. А пока дело решалось в Петербурге, Дмитрий Милютин получил несколько благодарственных писем за военную службу, хотя в послании генерала Гурко ничего не говорилось об «усердии и полезной службе».
В конце ноября возвратился в Ставрополь генерал Гурко, он по-прежнему был весьма любезен с Милютиным, у которого работы было не очень много: он, как и прежде, подготовил план действий отряда на следующий, 1845 год, отредактировал его после замечаний начальства; затем была подготовлена обширная записка, в которой были изложены и мысли 1840 года, и мысли недавней записки об укреплении отдельных очень важных пунктов, как только что захваченная крепость Воздвиженская, около Урус-Мартана и Ачхоя в Малой Чечне. Милютина не покидала надежда, что и после его отъезда с Кавказа «останутся прочные следы двукратной моей службы в этом краю».
Высочайшее соизволение на рапорт Милютина последовало 10 ноября, но нужно было подыскать преемника на должность Милютина, но один офицер отказался, а другого никак не могли отыскать. Горемыкин предупреждал, что необходимо личное присутствие в Петербурге для устройства своих дел, а то можно оказаться обер-квартирмейстером пехотного корпуса в Вильне, о чем уже распорядился Николай Первый. Переписка между военным министром и князем Паскевичем затянулась, а в это время освободилась вакан сия профессора Военной академии по военной географии. Пока обсуждалась такая возможность для Милютина, Горемыкин тут же дал согласие от имени своего друга на эту должность, приостановив оформление его на должность обер-квартирмейстера в пехотный корпус в Вильне. «В этом случае Горемыкин оказал мне существенную, истинно дружескую услугу, – вспоминал Д.А. Милютин. – В тот самый день (28 декабря), когда я только ответил Г.Ф. Стефану, уже последовало высочайшее соизволение на новое мое назначение – профессором в Военную академию».
Конечно, у Милютина не было особых иллюзий относительно этой новой должности, работы много, при этом совершенно неизведанной, а служебная оплата крайне низкая, вряд ли хватит на обеспечение все растущей семьи. Труда он не боится, привык работать по много часов подряд, не выходя из кабинета, но Горемыкин и профессор Стефан упоминали о возможности совмещать с другими занятиями.
Дмитрий Алексеевич тут же написал отцу и Николаю, которые в ответ выразили удовольствие от скорой встречи и от назначения на почетную должность. «Надежда соединиться вскоре с тобой есть для меня не только бесконечная радость, но совершенное счастье, – писал Николай Алексеевич. – При теперешнем общем соединении нашего семейства в Петербурге ты необходим и для него, и для меня в особенности. О многом нужно мне с тобою, – и с одним тобой, – поговорить, посоветоваться, погрустить, порадоваться; одним словом – поделиться мыслью, чувством, словом».
7 января 1845 года поступило официальное распоряжение военного министра о переводе подполковника Д.А. Милютина в Петербург на службу профессором Военной академии. Пора было собираться к отъезду из Ставрополя.