Raised in the of South Deering on the Southeast Side of Chicago, Burge was the second eldest son of Floyd and Ethel Burge. Floyd was a blue collar worker of Norwegian descent and Ethel was an aspiring fashion writer of mixed Western European descent. Burge attended Bowen High School where he showed interest in the school's Junior Reserve Officers' Training Corps (JROTC). There he was exposed to military drill, weapons, leadership and military history.
He attended the University of Missouri but dropped out after one semester, which ended his draft deferment. He returned to Chicago to work as a stock clerk in the Jewel supermarket chain in 1966.
In June 1966, Burge enlisted in the army reserve and began six years of service, including two years of active duty. He spent eight weeks at a military police (MP) school in Georgia. He received some training at Fort Benning, Georgia, where he learned interrogation techniques. He volunteered for a tour of duty in the Vietnam War, but instead was assigned as an MP trainer. He served as an MP in South Korea, gathering five letters of appreciation from superiors. On June 18, 1968, Burge volunteered for duty in Vietnam a second time, and was assigned to the Ninth Military Police Company of the Ninth Infantry Division. He reported to division headquarters, where he was assigned to provide security as a sergeant at his division base camp, which was named Đồng Tâm by William Westmoreland. Burge described his military police service as time spent escorting convoys, providing security for forward support bases, supervising security for the divisional central base camp in Dong Tam, and serving a tour as a provost marshal investigator.
During his military service, Burge earned a Bronze Star, a Purple Heart, the Vietnamese Cross of Gallantry and two Army Commendation Medals for valor, for pulling wounded men to safety while under fire. Burge claimed to have no knowledge of or involvement in prisoner interrogation, brutality or torture in Vietnam. Burge was honorably discharged from the Army on August 25, 1969.