Lebuïnus was one of several missionaries from England who preached christianity in the Netherlands. In 768 the bishop of Utrecht sent him to the area near the river Ijssel. A first church was built in Wilp, a second followed shortly after, a small wooden church in the settlement that was to become Deventer. Already in 770 this church was destroyed by pagan Saxons. In 770 Lebuïnus rebuilt the church. A year later he died and was buried in his church. After this church was destroyed as well in 774, another missionary, Ludgerus (also known as Ludger and Liudger), rebuilt it in 776. The predecessor had been so completely destroyed that Lebuïnus' grave could not be found.

In 895 bishop Adelbold I of Utrecht settled in Deventer. His successor Balderik again resided in Utrecht, but he did order the construction of a stone church in Deventer in the 10th century. In ca. 1040 bishop Bernulfus had it rebuilt into a Romanesque basilica. This was a big church dedicated to Mary and Lebuïnus and had two towers at the front.

In 1235 and 1334 the church was destroyed by fire. The current church was built between 1450 and 1525 on the foundations of the Romanesque church of which parts were incorporated, including the crypt and other parts of the interior of the choir. The crypt is now the oldest part of the church, and is very similar in style to that of the St. Pieter in Utrecht.

In its current form the church belongs to the the Lower Rhine group of Gothic. It is a hall-church, meaning that all aisles are of equal height. The choir has an ambulatory which was built from 1480 until 1502. Like its predecessor, the Gothic church was planned to get two towers, only one of which was actually built, although it was not completed. In 1499 it was covered by a temporary roof. In 1613 a lantern, designed by Hendrick de Keyser, was placed.
In 1559 Deventer became the capital of one of several dioceses, newly founded by order of king Philip II of Spain. The St. Lebuïnus became a cathedral. Only between 1570 and 1577 a bishop, Egidius de Monte, actually resided here. In 1580 the protestants confiscated the church and covered the murals under a coat of white plaster. Twice it was returned to its original owners. The first time was from 1589 until 1591, when Spanish troops had recaptured the city. The second time was from 1672 until 1674, under French occupation. Once the French have left, the protestants took back the building.

In the 20th century the church has been restored several times. From 1905 until 1924 the exterior was restored, with much of the roofs being replaced. During a restoration of the interior from 1927 until 1952 many murals were rediscovered. From 1959 until 1970 the windows were restored. Between 1987 and 1990 parts of the exterior are once again restored, while the murals in the interior are preserved.

Next  to the church, looking like an extension of the northern side-aisle, are the remains of the Mariakerk (church of Mary). This church was probably built at the end of the 13th century. It was a parish-church, while the much bigger St. Lebuïnus was a collegiate church. It was a basilica, with on its northern side a chapel which was built square on the nave, the Sacramentskapel. In 1511, after it had been decided to cancel the construction of a second tower of the St. Lebuïnus, the southern side-aisle of the Mariakerk was widened and connected with a passage to the northern side-aisle of its big neighbour. After the Reformation the Mariakerk lost its function and fell into decay. The roof of the nave and all vaults were demolished. The northern side-aisle was demolished in 1612. The resulting space was filled with houses which were built against the remaining church walls. In 1647 the southern side-aisle became an armoury. The Sacramentskapel, which was now seperated from the rest of the church, was rebuilt into two houses. In 1891 part of it burned down and was replaced. In the 20th century the Mariakerk was rediscovered as something special, and its ruins were restored.