A primeira menção que há do local da praça remonta ao ano de 1753, quando ali foi construído um cemitério. Seu lado sul foi o primeiro a ser ocupado, construindo-se ali a Igreja Matriz. Em consequência disso, seu nome passou a ser Praça da Matriz. Pouco tempo depois, em 1772, aparece no primeiro mapa da pequena povoação que era Porto Alegre em seus primórdios, como Praça do Novo Lugar. Quando a capital da capitania foi transferida de Viamão para Porto Alegre, a praça foi escolhida para abrigar o Palácio do Governador, concluído em 1789, passando a ser conhecida também como Praça do Palácio da Presidência. Ao lado do Palácio, apareceu em 1790 a Casa da Junta ou da Real Fazenda e, entre 1837 e 1839, ao lado da Matriz, a primeira Capela do Divino Espírito Santo.[3]
Estabelecendo-se lentamente, a praça até 1840 não passava de uma elevação erodida, sem qualquer adorno. Nessa década foram então construídas as primeiras calçadas, e na segunda metade do século XIX, passada a agitação causada pela Revolução Farroupilha, quando a cidade foi sitiada por dez anos, outros edifícios importantes foram sendo construídos no seu entorno, como o Palácio do Ministério Público, a sede da Sociedade Bailante, a primeira hidráulica da cidade, a primeira sede da Intendência municipal, o Theatro São Pedro e seu edifício gêmeo (esta sede do Palácio da Justiça (mais tarde destruído em um incêndio), e a Junta Criminal.[4]
Em 1858, seu nome foi alterado para Praça Dom Pedro II, por ocasião da visita do Imperador à capital da província. Logo depois foi instalado o Chafariz do Imperador com estátuas de mármore, que simbolizavam os grandes rios da Bacia do Guaíba, transferidas em 2014 para a Hidráulica Moinhos de Vento, e resolveu-se dar início à arborização. Entretanto, uma fotografia tomada após 1870 mostra apenas poucas palmeiras.[1]
O ajardinamento só foi empreendido de fato entre 1881 e 1883, incluindo 20 oliveiras vindas de Portugal. Em 1885 recebeu o Monumento ao Conde de Porto Alegre, depois removido para a praça que leva seu nome, a Praça Conde de Porto Alegre. Em 11 de dezembro de 1889, um decreto municipal alterou o nome do logradouro para Praça Marechal Deodoro, que conserva até hoje.[1] Em 1896, o antigo Palácio do Governo foi demolido para dar lugar a uma sede mais ampla e luxuosa, o atual Palácio Piratini.[5]
Posteriormente, a Praça recebeu grandes melhoramentos, concluídos em 1919. Em 1927, onde se localizava o antigo prédio da Assembleia Legislativa, foi construído o primeiro Auditório Araújo Vianna, para concertos da banda municipal, que foi demolido na década de 1960 para erguer-se em seu lugar o moderno Palácio Farroupilha, sede do Poder Legislativo do Estado.[1] Nas vizinhanças imediatas da Praça da Matriz encontram-se ainda o Solar dos Câmara, o Museu Júlio de Castilhos e a Biblioteca Pública do Estado, todos em edificações históricas.[4]