Fundada em 1930, com o lançamento da pedra fundamental, a construção durou dez anos. Foi inaugurada em 21 de setembro de 1947, pelo então Presidente da República General Eurico Gaspar Dutra. Inicialmente, a secretaria da nova escola foi responsável pela parte burocrática das Escolas da Zona Rural, e por isso recebeu o nome de “Escolas Reunidas Cyríaco Félix de Toledo”.
Pelo Decreto nº 148/75 de 13 de agosto de 1975, as Escolas Reunidas Cyríaco Félix de Toledo passaram a ser chamadas de Escola Municipal Cyríaco Félix de Toledo, com autorização para o Ensino Fundamental I e II, e para a Educação Infantil, a partir de 3 de outubro de 1991.
É a mais antiga escola municipal de 1ª à 4ª série (Atualmente Ensino Fundamental I) com prédio próprio, sendo que, em 1970, foram implantadas as séries de 5ª a 8ª (Atualmente Ensino Fundamental II), e posteriormente o Ensino Médio (Desativado no ano de 2000).
O nome da escola homenageia o grande trabalhador pela Educação do Município, Sr. Cyríaco Félix de Toledo, que foi prefeito desta cidade no período de 1919 a 1926, deixando significativas contribuições para o município de Corumbá, tais como: Praça da República, Escola de Comércio Corumbaense, Mercado de Emergência e o Gabinete Corumbaense de Literatura. Junto com os professores José de Souza Damy e Maria Leite Pedroso, fundou o primeiro Ginásio Público de Corumbá, sendo mais tarde batizado como “Ginásio Estadual Maria Leite”.