Aalborg was already a town in the mid-10th century, with a fine position on the east-west Lim Fjord that served as a trade route between the North Sea and the Baltic until the 12th century, when the west end of Lim Fjord was closed by sand drifts. Aalborg became the regional trade center for northern Jutland. The famous Viking burial site at Nørresundby across the Lim Fjord indicates that this was a populated area of Denmark long before the town appeared on the fjord.
Christian missionaries probably arrived sometime in the 9th century since nearby Viborg and Aarhus have evidence of Christian activity. In 948 Denmark was divided into dioceses and Aalborg in time fell under the See of Viborg. Of the earliest churches in Aalborg no trace remains. They would have been constructed of timber and been very small. Many times stone churches were built on the same location as the first churches, but direct evidence of an earlier "Viking" church has not been found.
In the crypt of Budofi Cathedral visitors can see the remains of the large stones used for the original church that was built at the direction of Bishop Eskil of Viborg no later than 1132. The first church was much smaller than the current church since it was a parish church. It consisted of a short nave and choir built in Romanesque style. That means it had half-round arches supporting a flat timber ceiling.
The existing Budolfi Cathedral (Danish:Budolfi Domkirke) was built in the last decades of the 14th century over and around the original St Budolfi Church and was listed for the first time in the Atlas of Denmark in 1399. The church was named after St Botolph, an English abbot and saint. His reputation as a learned and holy man in Anglo Saxon England as the patron saint of farmers and sailors made him a popular saint in pre-Reformation Denmark. His remains were venerated at Westminster Abbey, Ely, and Thornley Abbey. No references are made to relics of St Botolphus at Aalborg, but it was not uncommon for churches to be named after the relics of the most famous person the church possessed. Other churches in Denmark and southern Sweden have also been named after him including St Bodel and St Bodil, other Scandinavian forms of the name Botolph.
The church was constructed in the Gothic style out of Denmark's most common building material, large bricks. The nave and choir measure at present 56 metres (184 feet) in length and 22 metres (72 feet) wide, exclusive of the weapons porch and extensions.
Aalborg was the center of Skipper Clement's Rebellion of 1534. Clement Andersen, known as Skipper Clement, led the peasants and a few nobles of Vendsyssel in a peasant uprising that spread throughout Jutland. The peasants were trying to influence the selection of the next King of Denmark after the death of Frederik I. The abrupt truce with Lübeck freed up royal troops who chased the peasants all the way back to the walls of Aalborg. The royalist troops stormed the gates and commenced the sack and bloody slaughter of the rebels and citizens of the town. Just two years later Denmark became officially Lutheran. Due to its rural character and distance from Copenhagen, northern Denmark held onto elements of its Catholic past longer than other parts of Denmark. In 1554 Aalborg was made a diocese and after consideration St Budolfi Church was made the seat of the Bishop of Aalborg.
By the late-17th century two other churches in old town Aalborg, Our Lady's Church (Danish:Vor Frue Kirke) and the Abbey Church (Danish:Klosterkirken), were deemed to be superfluous for the few thousand residents of Aalborg. Our Lady Church, the oldest of the three, was determined to be unstable, and it was torn down. By 1800 the Abbey Church and tower were dismantled, and the stone was used to expand nearby Aalborg Castle. Budolfi Cathedral's tower is the only one of the original three church towers that are visible on the Aalborg city logo.
The tower was added to the west front in 1779 with funds given by Jacob and Elisabeth Himmerig. The square 28-metre-high (92-foot) brick tower is topped with a 35-metre (115-foot) metallic Baroque cupola and spire. Four identical clock faces were installed on each of the four sides of the tower in 1817. The south side has a sundial mounted on it as well. The tower houses four bells. The oldest cast in 1681 by Rudolph Melchior. The largest bell was cast by B. Løw and Son in 1892. A third bell was cast in 1926 by ... Smithske. The latest addition was the 1979 Petit and Fritsen bell.
In 1899 a sacristy was built onto the north side aisle.
During 1942 and 1943 the choir was extended 14 meters and the ceiling vaulting raised. A chapel was also added to the north side.
The main altar piece was added in 1684, a gift of Niels Jespersen and his wife Margareta Erichsdatter. It was carved by Lauridtz Jensen of Essenbæk Abbey near Randers. He also carved the pulpit. The altar was restored in 1980. The altar candelabras were given by Jens Christense and his wife, Mette Christensdatter, in 1686. Budolfi Cathedral received the gift of an altar carving from c. 1450 which is placed in the north transept. It came from the estate chapel of Holckershavn also known as Elleborg in southern Jutland.
The black and white marble baptismal font was given to the church in 1728, a gift of the widow Maren Grotum Von Pentz.
The pulpit (1692) was a gift from the first apothecary at Jesn Bangs Hus in Aalborg, Johannes Friedenreich and his wife, Magdalena Calow. It was carved by Lauridtz Jensen.
The ornate Baroque organ façade was constructed for the Hartvig Jochum Müller organ in 1749. The organ has been restored and expanded several times, the latest in 1959 by Th. Frobenius & Sons.
Several epitaphs have been preserved as examples of what once lined the aisles of the church. The 1583 epitaph for Karine Hansdatter is a fine example of renaissance work. The epitaphs for Jacob and Elizabeth Himmerig in 1773 and 1774 are examples of neo-classical design and commemorate the churches greatest benefactors.