In 1858, the newly constituted Burial Board for Birmingham obtained an order to close all the existing cemeteries in Birmingham, most of which were overcrowded. They advertised for a single, large plot of land, far enough outside the centre to avoid being quickly swallowed by the city's expansion. The following year, they obtained the current 40 hectare site at Witton, 4.5km from the city centre, on a west and south-facing slope overlooking the valley of the River Tame.

The board drew up general guidelines for the layout of the site, but the detailed design was put out to tender. The main contract was awarded to Richard Ashwell, superintendent of London Road Cemetery, Coventry, and former assistant gardener to Joseph Paxton at Chatsworth. He specified a layout composed of square plots, with wide avenues and walks between them, planted with “hollies, scarlet thorn, weeping ash, etc.”

Designs for the buildings, including the lodge, railings, gates, boundary walls, and two chapels (Anglican and Nonconformist) were accepted from R Clarke of Nottingham. The buildings were constructed by the Nottingham builder C Wright.

The cemetery was consecrated and opened for burials in 1863. The same year, the Roman Catholic community obtained permission to build a chapel on part of the cemetery allocated for Catholic burials. In 1868, one hectare at the north-east corner was sold to the Jewish community for a dedicated cemetery, with its own entrance, lodge and prayer hall. An additional lodge was constructed at the south-west corner of the site in the late 19th century.

The Roman Catholic chapel and the Nonconformist chapel were both demolished in about 1980. A new cemetery office was constructed in 2000. The city has expanded beyond the original predictions, and the cemetery is now surrounded by a mix of industrial and residential properties.