Galveston architect N. J. Clayton designed a twin-towered Gothic Revival church for Victoria's oldest Catholic parish, founded by Don Martín de León in 1824. Construction of the limestone church began in 1898 but was suspended in 1899. When building resumed in 1903, San Antonio architect Henry T. Phelps simplified Clayton's design, retaining his overall profile but substituting the awkward quatrefoils that frame tower windows and the exaggerated gablets above with Clayton's more assured detailing.
St. Mary faces Market Square, the other public square of the original townsite. The Victoria City Hall and Public Safety Building of 1966 by Christopher Di Stefano and Associates fills up the west side of the square, leaving the east side open as a surface parking lot.