Joseph Henry Lewis was born on March 7, 1944, in Knightdale, North Carolina. In 1962, Lewis enlisted in the US Marine Corps. He was stationed at Marine Corps Air Station Cherry Point in Havelock, North Carolina from July 20, 1962, to April 12, 1964. He studied Shōrin-ryū Karate with , John Korab, Chinsaku Kinjo and Seiyu Oyata while stationed in Okinawa between May 21, 1964 and November 29, 1965, earning his black belt in a mere seven months. He was one of the first Marines stationed in Vietnam, there meeting Anthony (Rocky) Graziano. From February 7 to July 14, 1966, he was stationed at Marine Corps Base Camp Lejeune, North Carolina, at which time he was released from active duty. Upon returning to the USA, he began a winning tournament career. From 1967 to 1968, he studied privately with the influential Wing-Chun kung fu teacher, Jeet Kune Do founder, and Chinese/Hollywood movie legend Bruce Lee. Hong Kong cinema historian Bey Logan says Lewis was the original pick of Bruce Lee for the villain Colt in "Way of the Dragon", but that Lee and Lewis had a falling out before the film and thus Chuck Norris was tapped instead.