Иногородними в Области Войска Донского называли живших на её территории людей, которые не являлись потомственными донскими казаками. Общество было сословным, а потому казаки на иногородних практически не женились и не отдавали за них своих дочерей. Учились и жили казаки и иногородние фактически раздельно — имело место своеобразная сегрегация.
Род Дмитрия тем не менее всё же происходил из казаков, но не донских, а запорожских. После того, как в 1775 году Екатерина Вторая ликвидирована Сечь, они отправились на Дон.
Дед Дмитрия был кузнецом, а значит, человеком востребованным. Отец тоже перенял кузнечное мастерство. Братья же мальчика уже владели самыми разными профессиями: старший Иван стал учителем. Он больше всех помогал маленькому Диме освоить науку и не остаться «тёмным». Дело в том, что, помогая взрослым, мальчик с 9 лет в тёплое время года батрачил, а учился только зимой. В 1912 году он закончил три класса церковно-приходской школы, этим его начальное и среднее образование и ограничилось.
Диму влекли к себе машины. С помощью брата Ильи он освоил локомобиль с двигателем внешнего сгорания, который приводил в движение хуторскую молотилку. Илья работал при этом агрегате кочегаром, а Дима год состоял смазчиком. Затем двоюродный брат Спиридон, работавший у помещика Королькова шофёром, взял Диму к себе подмастерьем. Та он два года сначала мыл машину, потом ему доверили её смазывать, собирать и разбирать. Вскоре паренёк освоил её «сердце» — двигатель, систему подачи топлива и зажигание. Иногда после очередного ремонта при обкатке Спиридон давал брату немного проехаться за рулём. Радости не было предела.
В 1914 году грянула Первая мировая война. Старших братьев забрали на фронт, и дома, кроме Дмитрия, остались только мать, отец-калека и сестра. В марте 17-го пришло известие о свержении царя, затем в Петрограде к власти пришли большевики, и страна погрузилась в кровавую мясорубку Гражданской войны.
28 апреля 1919 года Дмитрий вместе с братом Ильёй и другом детства Иваном Рябко добровольно присоединились к 21-му кавалерийскому полку 4-й кавдивизии Семёна Михайловича Будённого, тот в это время действовал в районе реки Маныч. Остальные братья Лелюшенко вступили в ряды Красной Армии годом раньше — раздражённые заносчивым поведением казаков, «иногородние» тяготели к красным и охотнее присоединялись именно к ним.
За время войны Дмитрий большой карьеры не сделал — от рядового дослужился только до должности командира отделения. Начав с боёв на Дону и под Царицыном, он громил войска атаманов Мамонтова и Шкуро под Воронежем, освобождал Ростов, воевал против Врангеля и поляков, гонялся по Украине за отрядами батьки Махно. Дважды под Лелюшенко убивало коня, дважды он был контужен и один раз — ранен.
Наконец Гражданская война закончилась. Как отслуживший положенный срок, Дмитрий мог вернуться домой, но он решил строить карьеру военного командира: в 1923 году в Петрограде он поступил в Военно-политическое училище им. Ф. Энгельса, и по его окончании через два года стал политруком пулемётного эскадрона в родном 21-м кавполке 4-й кавдивизии.
Однако Дмитрию хотелось стать не комиссаром, а командиром, поэтому он в 1927 году экстерном закончил полный курс 2-го Ленинградского командно-кавалерийского училища, а два года спустя поступил в Военную академию им. М. В. Фрунзе. И это при конкурсе более десяти человек на место. Учась на третьем курсе, Дмитрий женился на студентке Института цветных металлов и золота Дзанатхан Гутновой. Вскоре она родила ему сына Бориса, в будущем ведущего инженера-ракетостроителя.
В 1933 году Лелюшенко закончил академию по бронетанковому профилю и получил назначение на должность заместителя начальника оперотдела штаба 1-й механизированной бригады.
Однако ему не хотелось на штабную работу. Лелюшенко бомбардировал начальство рапортами, обратился напрямую к своему бывшему комдиву маршалу Будённому, и тот пошёл навстречу — молодого командира направили командовать танковой ротой. Армия стремительно росла, кадров не хватало, а потому буквально за пять лет Лелюшенко «вырос» с комроты до командира 39-й отдельной лёгкотанковой бригады.