The building is executed in a meticulous Gothic Revival style, and was designated a National Historic Landmark for its architecture.

While the overall composition of the building is generally symmetrical, the 195-foot (59 m) clock tower on the left side of the principal facade gives an impression of asymmetry.

The interior centers around a large skylit atrium surrounded by four levels of cloister-like arcades, linked by a grand staircase.

The first City Hall, designed by Robert Mills and Maximilian Godefroy and completed in 1818 was demolished because it was considered structurally deficient.

By 1915, with the popularity of the Beaux-Arts style, proposals were made to demolish City Hall to create a mall aligned with the northern side of the Virginia State Capitol.