Beulah is an African American Cemetery established by the Vicksburg Tabernacle No. 19 Independent Order of Brothers and Sisters of Love and Charity, a fraternal order that had wide support among the black community, in 1884. The organization purchased fifty-two acres along the old Jackson Road (now Martin Luther King, Jr. Blvd.) for $1000 from Harvey and Lucy Shannon. Prior to the development of this cemetery, African Americans in Vicksburg were buried in church cemeteries or in private yards.

Today Beulah is a 14.5 acre rolling tract, abutting the Vicksburg National Military Park in Vicksburg. More than 5,500 graves are scattered across the grassy tree-studded cemetery. Erosion of the loose soil, common in Vicksburg has created swales and high points and a number of grave markers have fallen or been lost due to the movement of the land beneath them. Three dirt roads access the cemetery from the city street—the main road into the cemetery enters through a functional gate and skirts the southeastern edge of the property, while two drives lead off from this road, running along ridges into the cemetery proper. The cemetery property originally contained 52 acres, and today a section of the remaining 14.5 acres is forested, with grave markers among the trees.

This cemetery was listed on the National Register on 23 October 1992