This paper attempts to reveal little-known pages from the history of relations between the peoples of Central Asia and Korea based on materials derived from written sources and modern scientific literature, as well as from medieval wall paintings from the early medieval Afrasiab Palace of Varhuman, the ruler of Samarkand, and from stone sculptures of Sogdian figures contained in Silla royal tombs. Korea’s interest in the western lands led to its contact with Buddhism, which spread and later flourished in all three Korean kingdoms (Koguryo, Paekche and Silla). The spread of Buddhism in turn motivated a number of Korean monks to undertake pilgrimages to India via Central Asia. Hyecho, a young Silla pilgrim, left evidence of his journey via the South China Sea to India in 723 AD. Paul Pelliot discovered a report from Hyecho’s journey entitled Notes on Pilgrimage to Five Regions in India (Wang Wu Tianzhuguo zhuan) in the Dunhuang caves in 1908. Hyecho’s contributions are worthy of attention, substantially complementing knowledge available for this little-studied period in the history of South and Central Asia. The information contained in Hyecho’s manuscript is, in fact, considered the most significant work of the first half of the 8th century. Research regarding the relationship between Central Asia and Korea remains underdeveloped. Existing historical evidence, however, including the above mentioned Samarkand wall paintings, depicts the visits of two Korean ambassadors to Samarkand, and evidence from Silla tombs suggests the presence of diplomatic relations in addition to trade between the two regions. Overall, the history of the relationship between Central Asia and Korea yields new insights into how and why these distant countries sustained trade and diplomatic and cultural exchange during this early period. Taking into account Korea’s growing interest in Uzbekistan, especially in its history and culture, this article can act as a catalyst for studying the history of the two country’s relations.