Under the leadership of the Right Reverend Lawrence Scanlan (1843 - 1915), the first bishop of Salt Lake, the construction of The Cathedral of the Madeleine was begun in the year 1900 and completed in 1909. On August 15 of that year, the cathedral was dedicated by Cardinal James Gibbons of Baltimore. The architects were Carl M. Newhausen and Bernard O. Mecklenburg. The cathedral combines a predominately Romanesque exterior with a Gothic interior. The property on which the cathedral sits was purchased in 1890 for $35,000. The cost of the cathedral construction itself was $344,000.

The exterior of the cathedral remains substantially the same today as it was in 1909, except for the addition of a tympanum over the main doors and the double flight of steps leading to the main entrance. Renovations on the exterior took place between 1975 and 1980 under the leadership of The Most Reverend Joseph Lennox Federal, sixth bishop of Salt Lake City. These including putting a new copper roof on the building, protecting the porous Utah sandstone from further erosion and restoring the gargoyles.

The interior of the cathedral was largely created under the leadership of The Right Reverend Joseph S. Glass, who became Bishop of Salt Lake in 1915. A man of refined taste and strong artistic sensibility, Bishop Glass enlisted the aid of John Theodore Comes, one of the leading architects in America at the time, to undertake beautification of the original plain interior. The Comes interior, begun in 1917, was inspired in great part by the Spanish Gothic of the late Middle Ages. the colorful murals were added at that time, as was the dramatic polychrome evident throughout the building. The ornate reredos shrine of St. Mary Magdalen and the various shrines were notable features of the Comes renovation.

Under the leadership of The Most Reverend William K. Weigand, who was appointed bishop of Salt Lake City in 1980, a much needed restoration of the interior, which had suffered the effects of dirt and pollution in the intervening decades, was planned and executed. For this project, the services of the firm of Beyer Blinder Belle of New York were retained. This renovation and restoration, the most extensive in the cathedral's history, took place between 1991 and 1993 at a cost of $9.7 million and involved every aspect of the interior.

This included renovation of the liturgical elements of the cathedral to bring them into conformity with the liturgical reforms that followed the Second Vatican Council (1962-1965), chiefly building a new altar in a more prominent location in the midst of the congregation; giving a new centrality to the bishop's chair; providing a separate Blessed Sacrament chapel; and adding a more ample baptismal font.

Additional elements involved a seismic retrofit to strengthen the building against earthquake damage; the rebuilding of the lower level of the cathedral, including Scanlan Hall; the creation of a new annex entrance to the cathedral; and the construction of a new cathedral plaza.

The renewed building was formally rededicated on February 21, 1993. The cathedral is listed on the Utah Register of Historic Sites and the National Register of Historic Places.