Дмитрию Милютину прежняя его должность не нравилась, друзья за это время получили новые назначения, разъехались кто куда, офицеры гвардейского Генерального штаба были в зимнее время мало заняты службой, и Дмитрий Милютин начал изучать международное право, политическую экономию, изучал общий курс военных наук, курс полевой фортификации, много читал, размышлял над прочитанным. Задумал издавать новый военный журнал, проект журнала был представлен в высшие инстанции, но проект не был утвержден высочайшим соизволением императора. Положение Дмитрия Милютина не радовало, даже часто бывая среди знакомых своих друзей, Милютин скучал: сердце его стремилось к семейству генеральши Понсэ, она принимала по средам, вроде бы он зачастил туда, но потом одумался: а вдруг Наталья Михайловна, которую он любил, не примет его, пойдут насмешки и дурацкие шутки на этот счет. И он какое-то время перестал туда ходить… Но сердце его рвалось к генеральше Понсэ, к Наталье Михайловне. Хандра не отпускала его. А его необеспеченное состояние не позволяло ему впрямую предложить руку и сердце Наталье Михайловне, уж не говоря о генеральше как главе семейства, но он «все больше поддавался непреодолимому влечению».

В Петербург приехал генерал Грабе и полковник Норденстам с планом борьбы русских войск на Кавказе, с предложением подчинить ему войска не только Кавказской линии и Черномории, но и отряды на Северном Дагестане и Черноморской береговой линии, которые подчинялись генералу Головину. Шамиль по-прежнему властвовал на Кавказе. Генерал Головин тоже представил план действий русских войск на Кавказе на 1842 год. Но торжествовал генерал Грабе, хотя император тут же приказал военному министру князю Чернышеву ознакомиться с положением на Кавказе, лично побывав на месте активных действий против Шамиля. Милютин не раз виделся с генералом Грабе и полковником Норденстамом, они звали его на Кавказ, но конкретного места не предлагали. А летом 1842 года начались неожиданные перемены на Кавказе. Министр Чернышев доложил императору положение на Кавказе «в черных красках». Император приказал сменить генералов Грабе и Головина на генерала Нейдгарта и генерала Гурко. Генерал Гурко, получив от генерала Ивана Федоровича Веймарна записку Милютина о действиях русской армии на Кавказе, почувствовал, что Милютин на Кавказе был бы очень полезен, Норденстам займет место начальника штаба, а на его место обер-квартирмейстера войск Кавказской линии и Черномории нужно назначить Дмитрия Милютина. Гурко прямо предложил Милютину это место.

Братья Владимир и Борис успешно учились в гимназии. Владимир был первым учеником в гимназии, был замечен министром народного просвещения С.С. Уваровым, присутствовавшим на экзаменах Владимира.

Вскоре Дмитрию Милютину, давшему согласие служить на Кавказе, пришлось представиться генерал-квартирмейстеру генералу Шуберту, затем военному министру князю Чернышеву, которые потребовали отправляться на Кавказ незамедлительно.

19 апреля 1843 года Дмитрий Милютин был приглашен на день рождения Натальи Михайловны Понсэ. Собралось многочисленное общество. Милютин был не в духе, Наталью Михайловну тоже не веселила собравшаяся родня, она хорошо знала, что Дмитрий Алексеевич должен уехать служить на Кавказ. Предоставим слово самому Милютину, который в своих воспоминаниях писал: «После чая, когда все гости оставили столовую и снова перебрались в гостиную, сама судьба так распорядилась, что я остался с любимою девицею вдвоем в столовой, без свидетелей, – тут, совсем неожиданно, – произошло между нами сердечное объяснение… Какое чудное мгновение – первое взаимное признание в любви! Какое неизъяснимое чувство испытал я, когда она с одушевлением и твердостью объявила, что готова за мною последовать куда бы ни бросила меня судьба и при какой бы ни было обстановке!.. Несколько минут объяснения совершенно перевернули все мое существо; мысли мои помутились; не сон ли это?.. Нет, это счастье наяву, счастье, какого я не смел надеяться…» В тот же вечер Дмитрий Алексеевич сделал предложение, которое и было принято.

Отец, братья, сестра и ее муж с радостью благословили этот брак, тут же поехали познакомиться с невестой и ее матерью. И закрутилась предсвадебная суета. Дмитрий Милютин тут же сообщил своему руководству, что в связи со свадьбой просит отсрочку.

Отец приехал из Москвы 8 мая, тут же поехал познакомиться с невестой и ее матерью.

Сначала состоялось православное венчание, а затем в квартире генеральши «совершена церемония по реформатскому обряду».

20 июня 1843 года подполковник Дмитрий Милютин и Наталья Михайловна прибыли в Ставрополь.

В Ставрополь Дмитрий Милютин с молодой женой Натальей Михайловной собирались недолго, и в начале лета они прибыли к месту своего назначения. Полковник Иван Иванович Норденстам занимал квартиру обер-квартирмейстера, но подготовил подполковнику жилище в солдатской слободке, на окраине города, пока не достроят ему новый дом.

Милютины ехали по прямой и пустынной улице, мимо редких одноэтажных домиков с соломенной крышей. Наконец остановились у одноэтажного дома из плитняка. «Пять окон по фасаду, – подумал Милютин. – Это уже не так плохо».

Милютины обошли весь дом, им отводились две комнаты, гостиная, спальня, передняя, две комнаты для мужской и женской прислуги, кухня во флигеле, где проживал и хозяин дома, штабс-капитан линейного батальона Щепило-Залесский. Несколько столов и стульев – вся обстановка дома.

– Это, конечно, не наше столичное жилище, – сказала Наталья Михайловна, – но жить можно.

– Ты помнишь, наш медовый месяц еще не закончился? – Милютин добродушно улыбнулся, нежно посмотрев на свою обаятельную жену.

– Ты сказал, что Ивану Ивановичу Норденстаму скоро новый дом отстроят, а нам дадут его квартиру? – спросила Наталья, словно бы не услышав слова Дмитрия Алексеевича про медовый месяц.

– Да, три-четыре месяца придется подождать… Полковник заранее предупреждал меня, что здесь, в Ставрополе, с квартирами бедственное положение, ну, ничего, потерпим, у нас ведь медовый месяц…

Наталья Михайловна бросилась целовать своего любимого.

«Хозяйство наше устроилось на самую скромную ногу, – вспоминал Дмитрий Милютин. – Прислуга состояла из денщика Родиона и горничной-немки, привезенной из Петербурга, да повара Евтея, данного мне отцом из числа бывших крепостных. В первое время мы обходились тем имуществом, которое привезли с собой; транспорт же с мебелью и другими предметами домашнего обзаведения, отправленный из Москвы только в конце июня, прибыл в Ставрополь уже в конце лета. Таким образом, первые месяцы мы прожили, можно сказать, на походной ноге».

На первых порах по обычаю Милютин представился губернатору генералу Ольшевскому и дежурному штаб-офицеру полковнику Кускову и вскоре приступил к исполнению своих обязанностей, а документов накопилось чрезвычайно много, и все неотложные. Положение на Кавказе изменилось. От наступательных действий русские войска перешли к оборонительным, надлежало укреплять оборону городов и местечек на линиях. Горцы подумали, что укрепление оборонительных линий – это от слабости русской армии, вели себя дерзко, нападали, но встречали их сильным упорным огнем. Так что время для укреплений всех линий было предостаточно.

Милютин со своими помощниками, а среди них было два начальника отделений, у штабс-капитана Мацнева занимались военными действиями и передвижением войск, а у штабс-капитана Ольшевского (будущий автор мемуарной книги «Кавказ с 1841 по 1866 год») – личный состав кадров, сведения о войсках, о крае, о неприятеле, о военных поселениях и казачьих станицах, велась переписка по устройству кордонных линий, занимались разработкой общих соображений относительно образа действий на Кавказе, комплектацией штатного расписания, а для этого нужны были рапорты для генерала Гурко, который отсылал их императору на высочайшее утверждение. Этим и занималась вся команда подполковника Милютина.