На первых порах по обычаю Милютин представился губернатору генералу Ольшевскому и дежурному штаб-офицеру полковнику Кускову и вскоре приступил к исполнению своих обязанностей, а документов накопилось чрезвычайно много, и все неотложные. Положение на Кавказе изменилось. От наступательных действий русские войска перешли к оборонительным, надлежало укреплять оборону городов и местечек на линиях. Горцы подумали, что укрепление оборонительных линий – это от слабости русской армии, вели себя дерзко, нападали, но встречали их сильным упорным огнем. Так что время для укреплений всех линий было предостаточно.
Милютин со своими помощниками, а среди них было два начальника отделений, у штабс-капитана Мацнева занимались военными действиями и передвижением войск, а у штабс-капитана Ольшевского (будущий автор мемуарной книги «Кавказ с 1841 по 1866 год») – личный состав кадров, сведения о войсках, о крае, о неприятеле, о военных поселениях и казачьих станицах, велась переписка по устройству кордонных линий, занимались разработкой общих соображений относительно образа действий на Кавказе, комплектацией штатного расписания, а для этого нужны были рапорты для генерала Гурко, который отсылал их императору на высочайшее утверждение. Этим и занималась вся команда подполковника Милютина.
Стояло лето, изнурительная жара, время отпусков и лечения открывшихся ран; многих членов команды не было в штабе, бароны Вревский и Торнау, капитаны Облеухов и Голенищев-Кутузов, штабс-капитан Веревкин были в отпуске или командировках. Несколько топографов, молодых офицеров и нижних чинов – вот и весь штаб в подчинении молодого подполковника.
В сентябре 1843 года Милютин представил генералу Гурко план разграничения районов местных управлений, штатное комплектование с определенными окладами содержания, все это было отправлено в Петербург, прочитано военным министром Чернышевым и получило высочайшее утверждение в ноябре.
Четыре года тому назад Милютин получил распоряжение включить магометанское население (туркмен, калмыков, ногайцев) в линейные казачьи войска, прирезать определенную часть земли, но дело так и не было доведено до конца в связи с переменой начальника края. Генерал Гурко вступил в должность 22 декабря 1842 года, и это дело тоже он должен был завершить. А раз назначили Милютина, то дело снова попало к нему. И Милютин вновь, как и в прошлые годы, предложил исключить магометанское население Кавказской области из казачьих войск.