Tae Kwon Do means Fist and Leg way. Tae = Fist, Kwon = Leg, Do = Way.
Many Tae Kwon Do practitioners will tell you that it evolved from an ancient Korean martial art which is hundreds or thousands of years old. But the truth is that there were various attempts after the second world war, in 1946, 1955 and 1957 by masters of not only Korean martial arts but also Japanese martial arts such as Shotokan, to unify and create a new Korean martial arts product. While controversial, it is in fact a well known truth that Choi Hong Hi trained in Shotokan Karate, and the naming of the original arts themselves presents them as essential brothers and sisters of Japanese Karate systems and Chinese Kung-Fu systems. From the entry on Japanese Wikipedia,
in 1940s during the Japanese rule of Korean Peninsula, Karate (空手, or “Empty Hand Martial Arts”) was taking hold under the name Kongsoodo (공수도, 空手道) and Tangsoodo (당수도, 唐手道, “Tang Dynasty Martial Arts”).
To backtrack on these namings, we need to understand the origin of Karate. Sakukawa Kanga (佐久川寛賀) from Ryukyu Kingdom (today's Okinawa) studies in China and developed martial arts called 唐手 (read “Tudi”), which translates to Chinese (Tang) hands. When Ryukyu Kingdom incorporated into Japan, Tudi faced extinction, but Anko Itosu kept it going by introducing it to local elementary and junior high schools. At the time, Tudi was renamed to Karate, which is the Japanese way of reading 唐手. As an educator Itosu thought emphasis should be placed more on 型 (kata).
As Karate gained popularity in mainland Japan, Gichin Funakoshi (船越義珍) of Shotokan (松濤館) changed the Chinese characters of Karate from 唐手 (Chinese hands) to 空手 (empty hands). The character 道 (way; read “doh”) was appended, similar to Judo. This reflects the consideration to militaristic time in the 20s. By the way Funakoshi was also school teacher from Okinawa and he was also really into 型 (kata).
When Karate was introduced to Korean Peninsula, some used politically correct 空手道 (Kongsoodo), and others the original 唐手道 (Tangsoodo). In 1944 Won Kuk Lee (이원국, 李元國) a pupil of Funakoshi opens Chung do kwan (청도관, 靑濤館) the first Tangsoodo school in Korea. Apart from the known fact that Lee studied under Funakoshi, the fact that 靑濤館 borrows a letter from Shotokan (松濤館) signifies that it's meant to be a direct lineage from Shotokan Karate. Choi Hong Hi (최홍희, 崔泓熙) also studied Shotokan Karate in Japan and has 2nd dan.
Choi kept practicing Karate after he went back to Korea, and later in Korean Army. In 1954, at the height of Korean War, Choi with 29th Infantry Division performed a demonstration in front of President Syngman Rhee. The legend goes that President praised the demonstration convinced that it was Taekkyeon. Fully aware of anti-Japanese sentiment, Choi had said that it was his original martial arts. Other account says that President has ordered the kwan leaders to unify to a single system so it could be introduced to Korean military. On April 11th of 1955, President Rhee certifies Taekwondo as the name selected by a committee headed by Choi, and on September 3rd of 1959 Choi renames Korean Kongsoodo Association to Korea Taekwondo Association. In other words, Karate was renamed to Taekwondo for political reasons, like Japanese renamed Chinese hands to Karate.
This by no means is meant to undermine the originality of Taekwondo relative to Shotokan Karate. As noted above, the lineage of Shotokan was influenced by educators who wanted to turn Karate into exercise. Meanwhile Taekwondo was introduced as practical combat martial arts to Korean army. So I'd imagine many modifications were needed.
Another interesting twist is the post-war internationalization and attitude difference towards sports. While the Japanese Karate stuck to traditions and kata, Taekwondo did not shy away from sparring and turning it into point-based sport, especially the South Korean WTF branch. This allowed Taekwondo to be included into Olympics wearing gloves and all while Karate remains not included.http://martialarts.stackexchange.com/questions/2498/history-of-shotokans-influence-on-taekwondo