Choi was born in Daegu, Korea, which was under Japanese control at the time. He started training in the martial arts at the age of 12 because his father was concerned—he wanted his small, physically weak son to be able to protect himself in the war-torn streets. Choi's first master was Dong Ju Lee. During his military service, Choi became a chief Instructor in the 20th Infantry Division and came into contact with General Choi Hong Hi when the military began to use taekwondo for unarmed combat.