Christianity was brought to Ukraine in the first century following the established Greek and Roman trade routes. There is evidence of this in the early Christian archaeological sites found on the north shore of the Black Sea. As in other parts of the Roman Empire, Christianity was persecuted and this impeded the development of the Church's organization, communications and structures. Nevertheless, the work of evangelization progressed. Pope St Clement I was exiled to Crimea by the emperor Trajan and in 101 was martyred there.

His remains were discovered centuries later by Saints Cyril and Methodius at Chersonese Taurica. Some of these were transferred to the Church of Tithes in Kyiv and the rest were returned to Rome. Until the Mongol invasions destroyed Ukrainian society, St. Clement had been a well-known saint in the area.

In the seventh century another pope, St. Martin I, was exiled to Crimea by an angry emperor. He died in Cherson in 655 and his tomb became a center of great popular devotion.

In the ninth century, Saints Cyril and Methodius began their missions to the Slavs after first visiting what is now eastern Ukraine on a mission to the Khazars. They were encouraged and assisted by the papacy, especially Pope Adrian II. Most of their activity was among the Slavic peoples of what is now Moravia (part of the Czech republic) but their importance lies mainly in their role as Teachers of the Slavs in which they developed literature and above all the alphabet which today is known as Cyrillic. In the nineteenth century they played an important symbolic role in the reawakening of Ukrainian nationalism. The remains of St Cyril now lie in the Church of St Clement in Rome.

Relations between Ukraine and the papacy began to develop seriously following the baptism of Ukraine in 988. Eastern Christianity had been brought from Constantinople and the Ukrainians were subject to that Patriarchate, which was still in full ecclesial communion with Rome. Emissaries were soon exchanged between Prince Volodymyr and Popes John XV and Sylvester II.

After the schism between Constantinople and Rome in 1054, direct contact continued throughout the middle ages. Innocent IV sent a mission to the Mongols in 1245 and negotiations with Princes Danylo and Vasylko Romanovich led to the coronation of Danylo as king of Rus by an Apostolic Delegate in 1253.

Following the fall of Constantinople to the Turks in 1453, the Patriarchate gradually lost influence in the Eastern Churches. With the establishment of the Moscow Patriarchate in 1588 the Ukrainians sought not only communion with Rome but also its patriarchal jurisdiction. With the Union of Brest in 1596, a new era began in which relations with Rome were constant and considerable. Papal diplomacy with the secular authorities under which the Greek Catholics lived was important in conserving their catholicity and also their ecclesiastical traditions.

After the upheavals that followed the first World War, the Apostolic Visitator and future Pope Pius XI, Achille Ratti, was unable to visit Soviet Ukraine. Under Soviet repression the support of Rome for the underground church was of vital importance but with the fall of the Soviet system the papal visitators were allowed to return and in 1991 formal diplomatic relations were renewed.