Prédio tombado pelo Instituto de Proteção ao Patrimônio Artístico e Cultural da Bahia (IPAC)
Em 20 de janeiro de 1898, foi lançada a pedra fundamental do edifício, pelo Ten. Cel. Domingos Adami de Sá, no local onde existiu a antiga casa dos jesuítas, cujas ruínas foram inteiramente demolidas.
Em 22 de dezembro de 1907 foi inaugurado o Paço, pelo mesmo intendente, segundo placa comemorativa existente na fachada. Os trabalhos de decoração e pintura foram feitos pelo artista italiano Oreste Sarcelli, e a iluminação, a acetileno, pelos irmãos Vita. O prédio tem uma área construída de 1060 m2, está localizado na Praça J.J. Seabra e ocupa a parte mais elevada da mesma, no centro histórico e comercial da cidade; possui quatro fachadas.
Descrição do IPAC (1988, p. 225): “Edifício de relevante interesse arquitetônico, construído para sede Municipal. Possui planta retangular, desenvolvida em dois pavimentos, em torno de um grande vestíbulo central, onde está localizada a escadaria, tipo imperial”.
O prédio sofreu várias reformas ao longo dos seus quase cem anos de existência. Entre os anos de 1912 e 1916, o edifício passou por uma grande obra de reforma, no governo do intendente Cel. Antonio Pessoa, como colocação de aparelhos sanitários e ampliação e reparo do mobiliário. Em 1919, apesar do pouco tempo de construído, ameaçava ruir, razão pela qual as repartições municipais foram transferidas para o Grupo Escolar. Em dois de julho de 1923, o prédio foi reformado e reaberto ao público pelo Intendente Cel. Eustáquio de Souza Bastos. Foram substituídos os assoalhos por lajes de concreto e a cobertura primitiva por três telhados paralelos.
O prédio do Paço Municipal foi construído no período de 1898 a 1907, em pleno florescimento da economia cacaueira. Foi um dos edifícios públicos do Estado mais luxuosos e melhor decorados e mobiliados à época. No pavimento superior funcionavam: sala do Conselho, gabinete do intendente, secretaria, seção de engenharia, salão nobre com pintura mural e salas de audiência. No térreo, funcionavam: as salas dos juízes do cível e do crime, posto médico, quartel e cadeia, segundo Borges de Barros (1981). Ainda segundo o mesmo autor, sua arquitetura parece ter-se inspirado no Paço dos Governadores, em Salvador, antes de sua última reconstrução, em 1912, e de igual inspiração neoclássica.
O nome do prédio, Palácio Paranaguá, é uma homenagem ao presidente da Província da Bahia que, no dia 28 de junho de 1881, através da Lei Provincial nº 2.187, elevou a Vila de São Jorge dos Ilhéus à categoria de cidade, permanecendo com o mesmo nome.