In 1552, a fire occurred in Kargopol, after which a new center of the city began to form, the Cathedral Square. The construction of the cathedral in honor of the Nativity of Our Lord and Savior Jesus Christ lasted ten years, and it was consecrated in 1562. On the site of the cathedral, there had previously stood a wooden church with the same dedication, and the fire only accelerated the decision of the Kargopol residents to build a stone temple. They spared no expense on this pious endeavor and invited craftsmen, presumably from Novgorod.

Thus, the first stone temple appeared in Kargopol, one of the first in the Russian North. The Nativity Cathedral remains little studied to this day. The assumption of the Novgorod origin of its builders has not yet been confirmed but is based on a superficial examination. Historian A. G. Melnik notes that the mixed type of masonry of the cathedral is characteristic of Novgorod architecture of that time. The architectural elements of the monument are made in the Novgorod style, and details such as thin cornices, cut corners of the altar pillars, and the design of the southern portal indicate the hand of Novgorod masters. However, these masters were influenced by Moscow and Central Russian architecture.

In 1765, another fire occurred in Kargopol, known as the "great" fire. The flames were so strong that, according to eyewitnesses, "logs were thrown across the river." The wooden buildings of the city burned completely, and stone structures were also damaged, including the Nativity Cathedral, which lost its domes and had its walls damaged.

The cathedral stood without repairs for five years while parishioners collected funds for restoration. Work began in 1770 and was completed only twenty-eight years later, although the main altar was re-consecrated as early as 1778. During this lengthy repair, the cathedral acquired features that have been preserved to this day.

In 1936, the cathedral was transferred to the Kargopol Historical, Architectural, and Art Museum-Reserve. Today, its walls are painted white, and only a small fragment of medieval frescoes remains on the western side. From the icons, only those installed after 1765 remain. An unusual element of the external structure is an iron beam in the shape of a hand protruding from the central stone drum, to which a chain was attached to support the central chandelier (the chandelier itself disappeared when the cathedral was closed).

Over time, the building of the cathedral has sunk into the ground by almost a meter.