Hall was born in Sardis, Mississippi and attended the University of Mississippi from 1905 to 1907. He then entered the U.S. Military Academy at West Point and was commissioned in 1911 as a second lieutenant of infantry. He served with the 20th Infantry Regiment until 1914, when he became an instructor in mathematics at West Point. In August 1917, he transferred to the 23rd Infantry Regiment, and then went to France for World War I. In March 1918, he became the adjutant of the 3rd Infantry Brigade, 2nd Infantry Division. He served at Verdun, Chateau Thierry, at Soissons in the Marne Offensive, in the St. Mihiel sector, and at Champagne in the Aisne Offensive. Hall received the Army Distinguished Service Cross, second to the Medal of Honor, for extraordinary heroism in action at Vierzy, France on July 18, 1918. His citation read: "At a critical time in the battle, when information was difficult to obtain, Lieutenant Colonel Hall, Brigade Adjutant, volunteered to report on the fighting in Vierzy, which was then in the hands of the enemy. Accompanying a group of French tanks, he entered the town under intense fire; and, during the advance, went forward through machine-gun fire and carried to safety a wounded man. He assisted materially in maintaining organization among the troops and established a first aid station at which many wounded were cared for, returning later to Brigade Headquarters with valuable information." In addition, Hall was awarded three Silver Star medals for gallantry. He also received the French Croix de Guerre for bravery on October 4, 1918, as well as the Legion of Honor.
Between the wars
After service with the Army of Occupation until August 1919, Hall returned to the United States with the 2nd Division, remaining as brigade and then division adjutant until 1922. He served on the Infantry Board from 1922 to 1923, and was then a student at the Infantry School. From 1924 to 1925, he attended the Command and General Staff School at Fort Leavenworth, where he was a distinguished graduate. He then served as an instructor at the Infantry School until 1929, when he entered the Army War College. After graduation from the Army War College in 1930, he spent two years in the Philippines. He then returned to Fort Benning as an instructor at the Infantry School from 1932 to 1937. From 1937 to 1940, he was Director of Ground Arms, Air Corps Tactical School, Maxwell Field, Alabama. In 1940, he took command of the 11th Infantry Regiment.