In 1852, Birmingham Town Council had inherited the old Public Office on Moor Street, from their predecessors the Street Commissioners, which the council used as their meeting place. It soon became apparent that this building dating from 1807 was not adequate for the needs of the growing town (which became a city in 1889) and that larger premises would be needed.
The land on which the Council House and adjacent Museum and Art Gallery are located was purchased in 1853. This land consisted of Ann Street which was home to properties such as the "Cabinet of Curiosities", a clothes shop advertised as "An exhibition for the curious observer of natural phenomena". The building had a clock tower topped with a flagpole. The top was castellated and the walls were whitewashed and adorned in advertisements and messages. The last tenants of the building were the Suffield family, ancestors of J. R. R. Tolkien.
The land was earmarked for development, however constant financial difficulties put all development on hold until 1871 when the council finally agreed to build offices on the site. A design competition was established and the council received 29 entries, which was disappointing in comparison to the 179 entries Sheffield and Birmingham received. However a decision was delayed by further financial difficulties. The council was then split over the Gothic entry by Martin & Chamberlain and the classical entry by Yeoville Thomason.
Thomason's design was chosen; his design featured a central section with a huge hexastyle Corinthian order porte-cochere carrying a balcony with an arch and tympanum high above, flanked by piers and columns which in turn carried a large carved pediment. However, amendments to the art gallery entrance and clock tower were made. The clock and tower are known locally as "Big Brum". Construction commenced on the building in 1874 when the first stone was laid by the then mayor Joseph Chamberlain. The building was completed in 1879 and cost £163,000 (equivalent to £17,630,000 in 2021). A debate was held to decide the name of the building: the options were The Municipal Hall, Council House and Guildhall.
The Council House was extended almost immediately, in 1881–85. The architect was again Yeoville Thomason. This was a combined art gallery, museum, and the home of the corporation's Gas Department, whose budget subsidised the building, as legislation limited the expenditure of ratepayers' taxes on the arts.
Above the main entrance, which faces Victoria Square, the tympanum contains a mosaic by Salviati Burke and Co. of Venice. Above that, the pediment shows Britannia receiving the manufacturers of Birmingham. Victoria Square itself was once occupied by Christ Church, a building which was demolished in 1899.
The Council House was extended a second time in 1911–19 (by architects Ashley & Newman) with a new block to the north and connected to the original building by an intricately designed archway (internally a corridor). The archway or bridge slightly resembles The Bridge of Sighs in Venice. The extension contains the Feeney Art Galleries.