A few Catholics lived in the Hampton Roads area in the seventeenth century, but the major influx came with the arrival of French immigrants to Norfolk in 1791. On the site of the present church a small wooden chapel was built, and then replaced in 1842 by a Greek Revival structure that burned December 8, 1856. In 1991 Pope John Paul II designated St. Mary's a “minor basilica” in recognition of its special significance as the city's oldest Roman Catholic church. Currently the church is home to the area's largest African American Roman Catholic congregation.
St. Mary's, although sometimes attributed to James Renwick, is the work of Patrick Charles Keely, an Irish-born architect who built extensively for the Catholic Church in the United States. Like Renwick's design for St. Patrick's Cathedral, New York (1853–1858), however, St. Mary's draws upon French Gothic models. The focal point of the three-aisle basilica is its western tower and highly decorated steeple that soars 240 feet above the ground. Although the view of the west facade is partially obstructed by an on-ramp to I-264, the view of the nave and its spectacularly patterned slate roof from the elevated interstate is unsurpassed. Originally exposed, the brick walls of the exterior were stuccoed in the 1920s. The interior of St. Mary's was extensively modernized during the 1980s, but the architectonic progression of the clustered piers leading to the polygonal apse at the east end remains undisturbed. Above the low clerestory, the elaborate lierne vaulting, executed in plaster, is especially noteworthy. The stained glass windows were designed by Mayer and Company of Munich, and the organ was made by Ferris and Stuart of New York.