Stewart was appointed a brigadier general on November 8 and assigned to command the 2nd Brigade, 2nd Division, Columbus District, of the Confederate Department No. Two (the precursor to the Department of Tennessee), under Leonidas Polk. Stewart held this position from November 16 until that December, when his brigade was transferred to the Department's First Geographical Division, until February 1862. His brigade was returned to western Kentucky, briefly being added to John P. McCown's division, leading the defenses of the town at the Battle of New Madrid before McCown ordered it evacuated and withdrew down the Mississippi River. On April 1, Stewart's men joined Charles Clark's division, in Leonidas Polk's corps, of Albert Sidney Johnston's Army of Mississippi, just in time for the Battle of Shiloh. There, Stewart led his brigade in first-day attacks on the "Hornet's Nest" area in the center of the Union line.