This structure replaced Benjamin Henry Latrobe's City Hall of 1817, which occupied the site set aside for the market and city hall and burned in 1871. The complex illustrates Americans' changing tastes. Cluss, German émigré architect and founder of the American Communist Party, designed a notable building which fronts on three streets. The facade on Cameron Street, in the French Second Empire mode common to American city halls in the post–Civil War years, was intended as the main entrance. The facade on North Fairfax Street originally housed the police department. It is fewer stories and more in an Italianate vein.
The tall steeple mass on North Royal Street is not by Cluss, but a design by the local architect Benjamin F. Price. It is supposedly a replica of Latrobe's original 1817 design, but one that he would only faintly recognize. The AlexandriaWashington Masonic Lodge financed the project under a separate contract with the builder, Edward H. Dulahay. Market sheds and commercial buildings on the south half of the block were torn down during urban renewal and replaced with the plaza. In the early 1960s a Colonial Revival structure that vaguely recalls the Governor's Palace in Williamsburg filled in the courtyard on the south side of City Hall. City Hall's interior has been gutted and refitted several times.