Через полтора года он состоял уже в полку своего отца. Но скорая смерть родителя лишила юношу прозаической протекции: теперь ему приходилось выбиваться в казачьи офицеры самому.
Отцовский полк стоял на Кавказской укрепленной пограничной линии, еще не представлявшей из себя тогда единого целого. Кутейников 2-й на Северном Кавказе побывал в двух длительных командировках: в 1779–1782 и 1784–1787 годах. Ему приходилось участвовать во многих стычках с «немирными» горцами, видеть на Кубани А.В. Суворова. Там же он и получил в 16 лет долгожданный чин есаула. Случилось это важное в его биографии событие 20 июля 1780 года.
Кавказская служба послужила ему самую добрую службу на будущее. Хотя она неслась в мирное время и о будущей Кавказской войне еще не велось речи, военные действия против «немирных» горцев не прекращались. Боевые качества казачьих заслонов постоянно проверялись многочисленными шайками горских разбойников-абреков. В документах того времени абреки именовались «хищниками».
Первая слава к Дмитрию Кутейникову, имевшему уже чин войскового старшины, пришла с началом «Второй екатерининской турецкой войны», которую можно с полным правом назвать Суворовской войной. Его полк входил в число войск Кинбурнского оборонительного района, которым начальствовал тогда генерал-аншеф Александр Васильевич Суворов, будущий генералиссимус всех российских войск.
Сражение на Кинбурнской косе 1 октября 1787 года начиналось так. Еще до рассвета на ее оконечности с турецких кораблей стал высаживаться янычарский десант. Янычары с большой поспешностью вырыли здесь первую линию окопов (ложементов) и от нее стали продвигаться вперед по песчаной косе к крепости Кинбурн, перед которой русские войска уже изготовились для встречи неприятеля.
Янычары раз за разом вырывали новые линии окопов от берега Днепровско-Бугского лимана до берега моря. Всего таких «перекопов» на косе ими было сделано пятнадцать. Они отставали друг от друга примерно на тысячу шагов и предназначались для стрелков.
Генерал-аншеф Суворов построил свой отряд для сражения в три боевые линии. На флангах, по берегу у уреза воды встали Донские казачьи полки полковника В.П. Орлова, подполковника И.И. Исаева и премьер-майора З.Г. Сычева. После сражения Суворов подпишет ведомость «Коликое число разных команд нижних чинов», из которой видно, что в деле с янычарским десантом участвовало 898 донских казаков (не считая офицеров) из общего числа 4405 человек.
Сражение на Кинбурнской косе началось в 15 часов. Первая линия русской пехоты атаковала подходивших к крепости Кинбург янычар. Султанский флот, приблизившись к косе, обрушил на косу шквал ядер, бомб и картечи. Суворов, руководивший боем, вел своих бойцов, шаг за шагом, от одной линии окопов к другой. Донцы проявили смекалку, обходя линии вражеских ложементов по морской воде, и в каждом таком броске оказывались в ближнем тылу у турецких стрелков, засевших в окопах.
В сражении Суворов был ранен дважды. Сперва картечь ударила его в левый бок, но генерал-аншеф поля боя не покинул. Когда уже начинало темнеть, вражеская пуля поразила его в левую руку и прошла насквозь. Генерал-майор Л.Н. Энгельгардт в своих мемуарах так описывает этот эпизод:
«…Суворов был ранен в левое плечо; он потерял много крови, и не было лекаря перевязать рану. Казачий старшина Кутейников привел его к морю, вымыл рану морскою водою и, сняв свой платок (офицерский галстук. –
Суворов сел на коня и опять возвратился командовать…»
Кинбурнская баталия закончилась около полуночи. Из десанта силой в 5 тысяч янычар на шлюпках спаслась едва ли десятая их часть. У неприятеля было отбито 15 знамен. Среди пленных оказалось несколько французских волонтеров в офицерских чинах – инструкторов. Императрица Екатерина II повелела на время отправить их в Сибирь, заметив при этом:
«…Дабы отбить охоту ездить учить и наставлять турок».
За «совершенную победу» на Кинбурнской косе Кутейников был награжден «Именной золотой медалью» на Георгиевской ленте и чином «донского полковника», то есть казачьего полковника. Шел ему тогда от роду всего лишь двадцать первый год.
В той «Второй екатерининской турецкой войне» он все же получил боевое ранение. Это случилось в 1790 году при штурме казалось бы неприступной Измаильской крепости. В своем рапорте главнокомандующему светлейшему князю Г.А. Потемкину-Таврическому генерал-аншеф Суворов среди отличившихся отметил и Кутейникова…
В 1791–1792 годах Донской казачий полк, в котором он служил, находился в Польше, оказавшись в гуще военных событий, связанных с ее 3-м разделом. Когда начались бои с отрядами польских конфедератов в Подолии, Кутейников отличился при взятии защищаемого им города Каменец-Подольский.
В 1798 году следует производство в армейские подполковники, а 28 октября следующего, 1799 года – в армейские полковники.