Родился 20 октября (2 ноября) 1901 года на хуторе Новокузнецовка (ныне Зерноградский район Ростовской области) в крестьянской семье. Украинец. Член ВКП(б)/КПСС с 1924 года.
Познав в раннем детстве нужду, юный Дмитрий Лелюшенко не мучился проблемой выбора, к кому присоединиться в годы Гражданской войны, и поэтому, когда весной 1918 года красный конник Б. М. Думенко, вернувшийся незадолго до этого с германского фронта, организовал на хуторе Весёлом партизанский отряд для борьбы с белоказаками, — стал партизаном. Отряд Думенко воевал более года, и в этих боях рос и мужал будущий военачальник.
С 1919 года Д. Д. Лелюшенко в Красной Армии — в составе 1-й Конной армии. Он участвовал в Воронежско-Касторненской, Донбасской и Егорлыкской операциях. По окончании Гражданской войны Д. Д. Лелюшенко остался на военной службе. Когда стали создаваться первые механизированные подразделения, он начал осваивать новую технику, и с этого времени его военная карьера будет связана с танковыми войсками.
В 1933 году Д. Д. Лелюшенко окончил Военную академию имени М. В. Фрунзе, после чего последовательно командовал танковым батальоном и танковым полком. Советско-финскую войну полковник Лелюшенко Д. Д. встретил на посту командира 39-й отдельной танковой бригады. В ходе боёв с белофиннами танкисты комбрига Лелюшенко активно помогали стрелковым подразделениям, штурмовавшим «линию Маннергейма» и многочисленные укрепления противника.
Начало Великой Отечественной войны застало его командиром механизированного корпуса. Вел свой корпус в бой под Двинском. В августе 1941 года он был назначен начальником Управления формирования и комплектования автобронетанковых войск — заместителем начальника ГАБТУ.
Но в октябре 1941 года Лелюшенко вызван к Верховному Главнокомандующему Сталину И. В., который приказывает ему срочно сдать дела по Управлению и принять 1-й особый гвардейский стрелковый корпус, который фактически необходимо было сформировать в самый кратчайший срок. Вновь сформированному корпусу была поставлена задача: остановить танковую группировку Гудериана, прорвавшую Брянский фронт и наступающую на Орёл… Девять дней воины 1-го гвардейского стрелкового корпуса героически сражались на полях Орловщины… В разгар боя за город Мценск, где особо отличились танкисты 4-й танковой бригады полковника Катукова М. Е., комкор Лелюшенко получает приказ о назначении командующим 5-й армией, которая должна занять оборону в районе Можайска… Однако, командовал он 5-й армией недолго — в одном из боёв был тяжело ранен, и его отправили в госпиталь города Горького (ныне Нижний Новгород).
После излечения, в середине ноября 1941 года генерал-майор Лелюшенко назначен командующим 30-й армией Западного фронта. Во время битвы за Москву 9 декабря 1941 года армия Лелюшенко, находившаяся на правом крыле Западного фронта, ломая ожесточённое сопротивление немецко-фашистских войск, перерезала железную дорогу «Москва — Клин», а затем, развивая успех, совместно с частями 1-й ударной армии блокировала в районе Клина крупную вражескую группировку. Наращивая темп наступления, уже 15 декабря 1941 года части 30-й армии заняли город, уничтожив врага…
Летом 1942 года участвовал в Ржевской битве. В ходе Ржевско-Сычёвской наступательной операции армия под командованием Лелюшенко понесла серьёзные потери, но не смогла выполнить поставленной боевой задачи.
В ходе контрнаступления под Сталинградом генерал-лейтенант Лелюшенко Д. Д. умело руководил вверенными ему частями 1-й гвардейской армии, за что был удостоен полководческого ордена Суворова 1-й степени.
В битве за Днепр войска 3-й гвардейской армии 4-го Украинского фронта (до 20 октября — Южного) под командованием Д. Д. Лелюшенко отличились в операции по захвату Никопольского плацдарма…
В марте 1944 года Д. Д. Лелюшенко вступает в командование 4-й танковой армией, которая под его началом, в составе 1-го Украинского фронта участвует в Львовско-Сандомирской, Восточно-Карпатской и Висло-Одерской операциях.
На заключительных этапах войны части 4-й гвардейской танковой армии Д. Д. Лелюшенко участвовали в Силезской и Берлинской операциях, завершившихся разгромом фашистской Германии.
5 мая 1945 года в Чешской столице Праге началось вооружённое восстание. Гитлеровцы намеревались потопить его в крови. Чешский национальный совет обратился по радио к странам антигитлеровской коалиции с просьбой о помощи… Ударная группировка 1-го Украинского фронта в составе 3-й и 4-й гвардейских танковых армий устремились на помощь братьям-славянам. Танкисты Лелюшенко, совершив в короткое время вдоль правого берега Эльбы неимоверно трудный 80-километровый марш-бросок, соединились 9 мая в Праге с войсками 2-го Украинского фронта, замкнув кольцо окружения. Спасли город и его жителей. 30 мая 1970 года благодарная Чехословакия удостоила Д. Д. Лелюшенко звания Героя ЧССР.
«Дмитрий Данилович Лелюшенко больше известен в наших Вооружённых Силах как общевойсковой командир, — писал в своих мемуарах „Генеральный штаб в годы войны“ генерал армии С. М. Штеменко. — Только в марте 1944 года, видимо, за свою энергию, оптимизм, подвижность он был поставлен во главе 4-й танковой армии и с честью прокомандовал ею до окончания войны. Генерал „Вперёд!“ — так называли Д. Д. Лелюшенко знавшие его».
По окончании Великой Отечественной войны генерал Лелюшенко Д. Д. занимал высокие командные должности в Вооружённых Силах СССР. С 1956 года он командовал войсками Забайкальского, а с 1958 года — Уральского военных округов. В 1959 году ему присвоено воинское звание «генерал армии». В 1960-64 годах — председатель ЦК ДОСААФ, с 1964 года — военный инспектор-советник Министерства обороны СССР. Депутат Верховного Совета СССР 1-го, 5-го и 6-го созывов.
Умер 20 июля 1987 года в Москве, где и похоронен на Новодевичьем кладбище.