The church, which is cruciform in plan, originally had an 8-bayed nave, though only the 2 E bays remain fully intact. The surviving Romanesque work of the church includes much of the south transept, the lower part of the crossing, the lower southern section of the north transept, and the eastern bays of the nave. Part of the Romanesque 3rd bay west of the crossing also remains, but the post-medieval west wall was built through the centre of it. Two capitals, found loose on a low external wall in the abbey grounds by Canon Weston in the late-20th century were taken into the Prior's Tower for preservation.

The Augustinian priory of St Mary in Carlisle was dissolved in 1540, though this appears to have had no impact on the fabric of the church. Following the Reformation, the east end, transepts, and first two bays west of the crossing of the church came under the control of the bishop, while the rest of the nave was used as a parish church. In the 17thc., the western 6 bays of the nave were taken down. Although there was another parish church nearby, St Cuthbert’s, the parish of St Mary’s did not combine with it, resulting in the east bays of the cathedral being partitioned off for its use. New, lowered ceilings were built and the bays subsequently fitted with seating (including galleries in the aisles) and necessary religious furnishings inserted. The area given over to St Mary’s proved too small for the parish, so a new parish church was built on another site in the old abbey grounds, near the Castle Street entrance, in 1868-70. As a result, the remaining portions of the nave were again opened up, the later ceilings removed, and this part of the edifice restored. Restorations of other parts of the building had already been undertaken some years earlier.

Tracing the history of Carlisle and its cathedral is complex. Domesday Book does not cover this area of England and early documentation is sparse. The early sources that survive, however, do provide important information. The Romans established a post called Luguvalium. After their departure there are few documentary references until the 7thc. when a religious community was established. Following this the city was generally referred to as Lugubalia or Luel. After the Viking attacks in the 9thc., Scandinavian settlement occurred, largely during the following century. Excavations have uncovered evidence of Viking burials, some in the area beneath the Romanesque cathedral. William the Conqueror appears to have gone through Carlisle, though it was not until 1092 that the Normans established a firm foothold there. In, or soon after this, Ranulf Meschin was given Carlisle and its surrounding area, which became the 'Honour' of Carlisle. After the White Ship disaster of 1120, when the Earl of Chester died, Ranulph became earl and moved to Chester. The Honour of Carlisle then passed to the Crown. Most likely in/about 1122-3 King Henry founded a house of Regular Canons, having visited Carlisle in 1122. No foundation charter for the priory survives. It has been suggested that a previous church may have existed on or near the site when the canons first arrived. In the only surviving pipe roll for Henry I's reign, for 1130-31, it is recorded that £10 was given by the king to the canons towards the construction of their church. In the same year money was paid for a wall around the city and reference made to silver mines. In 1133, the see of Carlisle was established. Before this, relevant churches had been governed by either the bishop of Durham or the bishop of Glasgow. The first bishop of Carlisle was Athelwold, who had been prior of Nostell, a position he continued to hold jointly until 1153/4. In the middle of the 12thc., a certain Walter is mentioned as prior of Carlisle and, about the same time, a person called Robert was archdeacon, though there may have been an archdeacon earlier than this, named Elyas. Athelwold died in 1156, after which the see remained vacant for nearly 50 years. During this period, its affairs were probably administered by the archdeacon. Henry II’s pipe rolls mention Carlisle for most years during his reign, beginning with those for 1158, in which year he visited Carlisle for the first time as monarch (he had previously been knighted in Carlisle by his uncle David I of Scotland in 1149). There is no early mention of construction work on the priory/cathedral church; but in the 1188 pipe roll work on the high altar and pavement is recorded, along with building work on the canons’ dormitory. Carlisle was under Scottish control during the period after 1136. In 1138, a provincial council of Scottish bishops took place in Carlisle under the papal legate Alberic. In the same year, Athelwold consented to the priory being affiliated with the order of Arrouaise, and confirmation was given for the free election of the prior. In 1157, Henry II took back control over the city. From 1136 onwards, David I of Scotland spent much time at Carlisle, eventually dying there in 1153.

Rebuilding of the E end began in the mid-13thc., but a fire in 1292 caused significant damage, necessitating further alterations. Changes to the E end continued throughout the medieval period. At an unspecified date, the central tower began to sink. It finally collapsed in the 14thc., destroying much of the north transept.

References in medieval documents concerning the person who became the 1st bishop of Carlisle show various spellings, including Athelwold, Aethelwold, Adelwald, Adhelwold, Adeluif, Eadulf, Adelold and Adulph.

It has frequently been suggested that Athelwold was prior of Carlisle before becoming bishop. Prior Walter's appearance around 1150 have led some scholars to suggest that Walter may have been the first prior after Athelwold, but Bishop Athelwold's 1138 confirmation of free elections of the prior of Carlisle may imply that a prior was soon to be elected or was already in office. Administration of the priory before 1138 is difficult to ascertain since relevant documentation is scarse..

It is not possible to confirm that the capitals on top of the E nook shafts at the E end of the nave arcades (at arch level) were originally intended. When the crossing piers subsided, adjacent stonework was dragged down. Some of the stonework at the E end of the nave was subsequently rebuilt and straightened, which included the capitals, the stone of which appears to be modern.

There is a noticeable change in the colour and carving of the stonework at the upper levels of the romanesque church. Edge rolls on arches and free-standing shafts first appear on the clerestory windows, and the interior clerestory capitals are carved differently from those carved at lower levels. All surviving romanesque work appears to be of 12thc. date, possibly (but not certainly) completed before Bishop Athelwold’s death in 1156. Reasons for the changes are yet to be fully understood. Money poured through Carlisle from the lead and silver mines, confirmed by the pipe rolls of Henry II and later. How this revenue may have affected the construction of the cathedral church and priory is unclear. A mint was also established in Carlisle in the 12thc., most likely as a result of Henry I's visit there in 1122. The earliest known minted coin from Carlisle is datable to about 1123.

Apart from the Pipe Roll records for 1130-31, no others survive until 1155, the first year of Henry II’s reign. The donation of £10 and reference to work on the priory in 1130, along with a royal confirmation of the chapel and manor of Warwick (Cumbria) to the monks of St Mary in York in 1131-2, confirmed by Bishop Athelwold sometime between 1133 and 1147, and another confirmation by Athelwold referring to the parochial of Warwick sometime between 1133 and 1156 combine to provide evidence for the likely period when the earliest surviving romanesque capitals at Carlisle were carved. The church at Warwick has 12thc. carving which appears to have been influenced by the cathedral.

Some carved work at the cathedral compare favourably with earlier carved work at Chester's St John's Church and Shrewsbury's abbey church. These include such features at Carlisle as the early capital forms, the N nave pier capitals, and the base mouldings with thin, prominent half-rolls.