The history of Christianity in Denmark started with Saint Willibrord's unsuccessful mission among the Danes in the early 8th century.
Runestones, place names and medieval personal names evidence that the pagan Danes worshipped the gods of the Norse religion. Thor was the most popular among the pagan gods: names referring to him can be documented even after the conversion. The name of Odense suggests that the town developed at a place dedicated to the cult of Odin. Persons with names referring to Freyr were also mentioned in runestones. The name of Lake Tissø is in all likelihood connected to the god Týr. A building, the remains of which were excavated at an early medieval settlement near Lake Tissø, was identified as a pagan temple by archaeologists.
Thor, Odin and the other deities were also mentioned in Icelandic sagas and Snorri Sturluson's Prose Edda which preserved much information of their cults and myths. However, it cannot be ascertained that the religious practices and legends of the pagan Icelanders and Danes were identical. Reports by Adam of Bremen, Saxo Grammaticus and other medieval Christian authors of the pagan Danes' religion are to be treated with caution, because they tended to attribute obscene and cruel rituals to non-Christians.
Scandinavian individuals came into contact with Christianity already before the fall of the Roman Empire, but historian Ian N. Wood writes that the "Christianisation of Scandinavia took the Church into relatively unknown areas". According to Alcuin, an Anglo-Saxon monk, Willibrord, who had proselytized among the Frisians, tried to convert Ongendus, King of the Danes, in the early, but failed. From the 820s, the Frankish monarchs tried to take advantage of internal strifes to increase their influence in Denmark. After being dethroned and exiled from Denmark, King Harald Klak sought refuge in the Carolingian Empire and agreed to be baptised in 826. Harald Klak returned to Denmark, accompanied by Ansgar, a Frankish monk from the Corbie Abbey. During the next two years, Ansgar carried out missionary activities in Denmark. He even bought young boys to teach them for missionary work. However, Harald Klak was again dethroned in 827, and Ansgar left Denmark.
The Diocese of Hamburg, which was established in the Carolingian Empire, became an important basis for missions among the nearby peoples, including the Danes. Ansgar, who was ordained the first bishop of Hamburg in 831, received a pallium (the symbol of his new rank of archbishop) in Rome in 840. He visited Denmark and purchased adolescent boys to educate them. After a Viking fleet destroyed Hamburg in 845, Ansgar was made bishop of Bremen, which gave rise to conflicts with the archbishops of Cologne, who claimed jurisdiction over the see of Bremen. Ansgar closely cooperated with Kings Horik I and II and continued his missionary work in Denmark. Although both kings remained pagans, Horik II allowed Ansgar to erect a church at Ribe and sent gifts to Pope Nicholas I in 864. After Ansgar died in 865, his successor, Rimbert, Archbishop of Hamburg-Bremen, continued his work.
Writing about a century later, Widukind of Corvey noted that "the Danes had long been Christians but they nevertheless worshiped idols with pagan rituals", suggesting that many Danes had by that time worshiped the Christians' God without regarding him as the only god. Changes in burial rites (including the spread of inhumation instead of cremation and the west-east orientation of the graves) during the last decades of the 9th century may be attributed to Christian influence, according to historian Michael H. Gelting, but no "indisputably Christian artefacts" have been excavated from the same period. During the 10th century, burial mounds yielding extensive grave goods show the resurrection of pagan burial rites.
Three German priests were ordained bishops to three Danish episcopal sees in Germany in 948: Liafdag to Schleswig, Hored to Ribe, and Reginbrand to Aarhus. Their consecration was most probably driven by an attempt to strengthen the position of the Archbishopric of Hamburg-Bremen which had up to the time had been suffragan bishops. No primary source suggests that the bishops visited their dioceses before the official conversion of Denmark to Christianity.
The official conversion occurred during the reign of King Harald Bluetooth, who mounted the throne around 958. According to the contemporaneous Widukind of Corvey, a priest named Poppo convinced him to accept that "there is only one true God" and the pagan deities were "in truth demons" by carrying a large piece of glowing hot iron in his hand without damaging it in about 965. Harald soon forbade his subjects to worship the pagan gods, ordering them to convert to Christianity. In contrast with Widukin, Adam of Bremen attributed the conversion of the Danes to a victory of the Holy Roman Emperor, Otto I, over Harald, but historian Michael H. Gelting writes that Adam's report is "spurious". Nevertheless, Harald's attempt to improve his relationship with the Holy Roman Empire in the early 960s contributed to his conversion.
Emperor Otto I spelled out the privileges of the bishoprics of Schleswig, Ribe and Aarhus in a charter in 965. The also confirmed the jurisdiction of Adaldag, Archbishop of Hamburg-Bremen, over the three bishops. A fourth bishopric was established in Odense a few years later. The four bishops fled to the Holy Roman Empire after Harald Bluetooth was dethroned by his son, Sven Forkbeard around 987. Adam of Bremen describes Sven's rebellion against his father as "a conspiracy to renounce Christianity", but no other source proves that paganism was restored in Denmark after Harald's fall.
Pagan burial customs disappeared in most territories by the end of the century, in the eastern regions in early . Instead of prelates subordinated to the archbishops of Hamburg-Bremen, Sven Forkbeard supported missionary bishops from England who had no permanent episcopal sees. Adam of Bremen claimed that missionary bishops from the Archdiocese of Hamburg-Bremen also worked in Denmark during this period, but he named only Odinkar the Elder who was a kinsman of the king.