A construção da primeira sede própria da Câmara Municipal teve início em 1575 e foi entregue, inacabada, no dia 14 de abril de 1576. Não se sabe precisamente sua localização, mas registros históricos indicam que ficava em frente à Igreja do Colégio dos Jesuítas.
O prédio era pequeno e rudimentar, construído por Álvaro Anes e feito de taipa de pilão, com telhado coberto de sapé. A construção era dividida em três partes. Numa extremidade ficava a Casa do Conselho; na outra, o depósito; no centro, havia a casa do meio, usada como cadeia. Com o passar do tempo, a edificação começou a ruir e os membros da Câmara pensavam em uma nova sede.
A partir de então, a Câmara Municipal de São Paulo funcionou em vários endereços,
em sedes próprias ou alugadas. De acordo com as ilustrações do livro “Paço Municipal de São Paulo – Sua história nos quatro séculos de sua vida”, de autoria do arquiteto Wilson Maia Fina, publicado na década de 1960, a Edilidade paulistana teve morada nos seguintes edifícios, entre outros:
1619: Rua São Bento
A Câmara instalou-se em prédio próprio, comprado de Francisco Roiz Velho, localizado provavelmente na Rua São Bento. Um esboço de tal edifício foi feito por dom Luiz Céspedes Xeria, governador do Paraguai, que por aqui passou em 1628.
1720: Largo São Francisco
Foi construído o novo Paço do Conselho. Ficava na esquina da Rua do Ouvidor com o então Adro de São Francisco (depois, Largo do Ouvidor). Em cima do sobrado, funcionava o Senado da Câmara, nome recebido a partir da elevação da Vila de São Paulo à categoria de cidade, em 1711, por d. João V. No andar de baixo, funcionavam a cadeia e o açougue. Foi a fórmula encontrada para solucionar os problemas gerados pelo precário abastecimento de carne e encarceramento de condenados. No entanto, em 1770, tal edificação estava em ruínas. A Câmara resolveu demolir seu prédio, mas não o fez de imediato. Naquele sobrado ficara a cadeia e, por isso, a rua passou a se chamar “da Cadeia Velha” (hoje, José Bonifácio).
1770: Rua do Carmo
Para solucionar rapidamente o problema de instalação, a Câmara, por ordem do ouvidor-geral, alugou duas casas na Rua do Carmo, considerada à época a melhor da cidade, pois nela estava o Convento do Carmo. Não há registros que indiquem seus proprietários. A Cadeia foi se alojar na Rua de São Bento, até que, para desonerar a Câmara, foi decidido, no ano de 1773, que ela deveria ser transferida para os porões dos casarões da Rua do Carmo. Em agosto de 1775, devido ao aumento do número de presos, foram tomadas as casas contíguas à Cadeia, junto à Igreja da Misericórdia, para também servirem de cárcere. Em 1777, devido às dificuldades da Câmara em obter verba da Fazenda Municipal, ao aluguel exacerbado e às péssimas condições da Cadeia, a Câmara mudou-se para um sobrado alugado na mesma rua, indo, no ano seguinte, para uma propriedade do Santíssimo Sacramento da Vila de Parnaíba, no Largo Episcopal, atual Pátio do Colégio. A prisão foi para um imóvel alugado na Rua Direita.
1787: Largo de São Gonçalo
No período de 1784 a 1787, foi construído o sobrado do Largo (ou Pátio) de São Gonçalo Garcia (Largo da Cadeia e Largo Municipal), atual Praça João Mendes, destinado a abrigar a Câmara, a cadeia e o açougue. Também foi inaugurado inacabado e sua conclusão só se deu em 1788, com a instalação definitiva do Paço, provavelmente em 1789, com a mudança dos papéis e do arquivo. O imenso casarão assobradado, com a frente voltada para o Largo, tinha, no andar superior, onde funcionava a Câmara, nove janelas, um balcão central, um sino e a imagem do padroeiro da Edilidade. Sobre ele, no encontro das empenas, ficava o brasão real. A parte inferior destinava-se à cadeia. As janelas das celas eram protegidas por fortes grades de ferro. Esse edifício passou por reformas e obras de embelezamento, realizadas após a elevação de São Paulo a Província, em virtude da criação do Reino Unido de Portugal–Brasil e Algarve, por d. João VI, após a vinda da Família Real para o Brasil. A Câmara funcionou nesse endereço durante 103 anos.
1877: Largo João Mendes
A Câmara realizou notável melhoramento urbano. Foi feito o ajardinamento do Largo do Teatro, atual Praça João Mendes (para a composição da mesma, foram anexados o Largo do Teatro e o Largo de São Gonçalo), e o presidente da Província, Sebastião José Pereira, fez reconstruir o edifício da Câmara, situado naquele Largo, retirando de lá a cadeia.
1897: Rua do Tesouro
Em março de 1897, o presidente da Câmara informou aos seus membros que o governo do Estado resolvera ceder para a Edilidade o prédio onde funcionava o Tesouro do Estado, situado na Rua do Tesouro, esquina com a Rua XV de Novembro. A data exata da mudança da Câmara para esse prédio é desconhecida, mas de acordo com publicações em jornais da época, teria ocorrido por volta de novembro do mesmo ano. A edificação foi construída por João Teodoro Xavier, em 1874, para abrigar a Escola Normal. Era um sobrado de dois andares, em estilo clássico, com largas janelas.
1914: Palacete Prates, na Rua Libero Badaró
O prefeito Washington Luís assinou contrato de locação do edifício situado na Rua Líbero Badaró, propriedade do Conde Prates. A Câmara e a Prefeitura ocuparam um dos dois prédios gêmeos que faziam parte do plano de reurbanização do Vale do Anhangabaú (concebido pelo urbanista francês Joseph Bouvard), projetados pelo engenheiro Samuel das Neves e por seu filho, o arquiteto Cristiano Stockler das Neves. No prédio, além do Plenário Municipal e do Executivo, alojaram-se diversas repartições técnicas da Prefeitura, ocupando toda a área que ia do porão ao sótão. Em 1930, ocorreram grandes convulsões políticas, encerradas com a vitória da revolução encabeçada pelo partido Aliança Liberal, que implantou no Brasil um governo provisório, com Getúlio Vargas no poder, que depôs a Câmara e nomeou interventores para administrar São Paulo.
1936: Palácio do Trocadero
O antigo espaço do Plenário Municipal, no térreo do prédio da Rua Líbero Badaró, estava todo ocupado com as repartições do Executivo. A Prefeitura aluga, então, os salões do Palácio do Trocadero, situado junto à Praça Ramos de Azevedo, para instalar o Plenário Municipal e os serviços do Poder Legislativo. Lá, eram realizadas sessões todos os sábados. Com a instalação do regime do Estado Novo (1937 a 1945), foram fechadas as Câmaras Municipais de todo o País.
1947: De volta do Palacete Prates
Em 1947, com o término da ditadura de Getúlio Vargas, foram realizadas eleições municipais. Eleita a nova Câmara, o Executivo paulistano prepara espaço no edifício onde funcionava o gabinete do prefeito, no Palacete Prates, para abrigar os 45 vereadores e todos os serviços do Legislativo. Com espaço reduzido, as autoridades municipais retomam a discussão para se construir o sonhado Paço Municipal.
1969: Palácio Anchieta
No local originariamente escolhido para a construção do Paço Municipal, foi edificada, na década de 1960, pela Construtora Alfredo Mathias S.A., a atual sede própria da Câmara Municipal de São Paulo. A inauguração aconteceu em 7 de setembro de 1969.