Catholic Cemetery was established by the Archdiocese of Mobile on December 18, 1848 when the first acreage was purchased north of Three Mile Creek by Bishop Michael Portier. It was founded to serve the needs of Mobile's Roman Catholic citizens after the Catholic section of Church Street Graveyard was filled to capacity after various yellow fever epidemics struck the city in the 1830s. The 1848 section covers 5 acres (2.0 ha) and features an unusual design consisting of three large concentric rings, instead of the more typical east-west configuration. The circular design surrounds a square plot dedicated to the Daughters of Charity, with a large marble monument in the center commemorating their sacrifices during a yellow fever outbreak in 1853. It was platted in this manner under the direction of Portier and was possibly executed by Claude Beroujon, who designed Mobile's Cathedral of the Immaculate Conception a decade earlier. The vast majority of burials predate the American Civil War.
By January 1866 the older section of the cemetery was full, prompting Bishop John Quinlan to purchase an additional 15 acres (6.1 ha) adjacent to the existing area. The new section was planned with a grid configuration, with the grave plots oriented to a new central drive. This section contains the plots for the Brothers of the Sacred Heart, Little Sisters of the Poor, and Sisters of Mercy. It contains the graves of Father Ryan and Admiral Raphael Semmes, which made it an important Confederate pilgrimage site during the late 19th and early 20th centuries. This area of the cemetery was expanded numerous times by land purchases in 1903, 1910, and 1921. In keeping with its main purpose as a religious burial ground, a permanent altar with a tall bronze Crucifixion scene was added by 1929 for the All Soul's Day Mass and Rosary.
The New Catholic Cemetery was opened to the rear of the older burials in 1948, greatly expanding the total acreage of the cemetery as a whole. This newest section offered perpetual care, something lacking within the older sections. The oldest areas of the cemetery became neglected, vandalized, and overgrown after this period, as family members died or moved away. Efforts to tame this area began in 1984, but it had become overgrown again within a decade. The archdiocese hired a crew to keep the cemetery clear of overgrowth in 1998 and 2006 saw the formation of the Friends of Catholic Cemetery, an organization dedicated to restoring the cemetery to its former state.