His subsequent battlefield commands were largely successful and his final actions in 1945 involved directing forces during the Red Army's attacks on both Berlin and Prague.
Such advancement was certainly partly due to the previous Soviet army purges, which had created a climate of opportunity, but also to the reputation he gained in Finland, where he had developed successful infantry cooperation tactics.
Whatever the reason, by spring 1941 Lelyushenko held the rank of major general and was designated commander of 21st Mechanized Corps, based within the Moscow military district with which he was obviously familiar.
On 23 June 1941, the day after Germany launched Operation Barbarossa, Lelyushenko set about reorganising his command to combat the specific threats of the German invasion.
This was noted by General von Manstein, in his book ‘Lost Victories’, where he describes the resulting German position as repeatedly becoming “quite critical” before they were able to regain control.
Attached to the Northwestern Front Lelyushenko earned himself the Order of the Red Star for his stubborn defence as Soviet forces nonetheless fell back 450 km in 18 days.
By late September the situation was critical and in an apparent change of responsibility Lelyushenko was now charged by the Stavka with forming a new 1st Guards Special Rifle Corps near the front line to defend the Moscow approaches and specifically the main highway from Orel.
Lelyushenko commanded part of this operation, launched during full darkness on 5 December and drove his men, specifically the 371st Rifle Division, forward, as usual from an advanced position near the fighting.
The capture of the Soviet capital had arguably ceased to be a practical proposition for the enemy, whose main offensives during the following year would be directed to the south and, eventually, Stalingrad.
In November 1942, after a year continuing to defend the Moscow approaches with much less difficulty than previously, Lelyushenko also went south, to take command of the 1st Guards Army.
During this period he was officially reprimanded for his habitual absence from his rear area command post, due to his insistence on attending the front in person.
Lelyushenko managed the armoured battle that followed, in which up to 1000 tanks were committed, defeating the German counter-attack and destroying much of the reserve involved, before ordering his forces across the Oder river.
During the last weeks of war, Lelyushenko took his armoured command first to the suburbs of Berlin, where they assisted in the advance into the Reich capital, and subsequently to Prague where they were also involved in a city assault.
He was not a consensual commander or given to delegating responsibility from afar, preferring to visit the front line and make his own decisions based on his own judgement.