Município foi criado com a denominação de Nossa Senhora de Nossa Senhora do Patrocínio e território desmembrado do de Araxá, ao qual pertencia, pela Provincial Nº 171 de 23 de março de 1840, ocorrendo a instalação a 7 de abril de 1842. Alguns anos depois, em 12 de janeiro de 1874, instalava-se a cidade de Patrocínio, e aí aparece o distrito de Cruzeiro da Fortaleza, como parte integrante do município de Patrocínio. Cruzeiro da Fortaleza teve início há mais de cem anos, em torno de um Marco de Santa Cruz, erigido pelo fazendeiro Antônio Luiz O topônimo da cidade originou-se justamente por causa desse Cruzeiro, juntamente com o nome do ribeirão que banha o município, o Ribeirão Fortaleza. E mais tarde, as terras naquele local e adjacências foram doadas ao município de origem (Patrocínio) para Patrimônio Público, pelo fundador do arraial que já o havia denominado de Cruzeiro da Fortaleza. Até 1910, o povoado de Cruzeiro da Fortaleza, pertencia ao município de Patrocínio, sem os foros de Vila Distrital. Segundo os dados constantes da Divisão Administrativa de 1911, aparece o distrito de Cruzeiro da Fortaleza, como parte integrante do município de Patrocínio, na qualidade de distrito e tendo a sua Vila como sede e Cartório de Paz e Notas. Na época, eram líderes da comunidade de Cruzeiro da Fortaleza o Senhor João Fernandes de Melo, Senhor Antônio Luiz da Silva Leite, Senhor Amâncio José da Silva, Senhor José Ferreira da Silva e Senhor Major Custódio Pereira.
O povoado era formado por um grupo de famílias, entre elas: Sr. Antônio Luiz da Silva Leite, Sr. Antônio Fernandes de Melo, Sr. José Pereira Nunes, Sr. Antônio Ribeiro da Silva, Sr. Antônio Ferreira Côrtes, Sr. Diomar Corrêa Côrtes, Sr. Gustavo Leite, Sr. José Luiz Siqueira. Cruzeiro da Fortaleza foi elevado à categoria de distrito por força da Lei 556 de 30 de agosto de 1911.Em 1912, dia 15 de Novembro, por Decreto do Senhor Governador do Estado de Minas Gerais, Dr. Júlio Bueno Brandão, foi instalado o distrito de Cruzeiro da Fortaleza, com vasta área territorial previamente doado pelo seu fundador, para seu patrimônio distrital na quarta década deste século, já dispunham dos prejudicados que lhe garantiam os foros do município. E não obstante, haviam seus filhos pleiteado esse direito, foi pretensão mal sucedida várias vezes. No Censo de 1920, o distrito ainda figurava como parte integrante de Patrocínio. Ainda pelos decretos Estaduais Nº 148 de 17/12/1938, Nº 1.058 de 31/12/1943 e ainda pela Lei Nº 1.039 de 12/12/1953 o distrito figurava como componente do município de Patrocínio. Ainda como distrito de Patrocínio, foi construído um Grupo Escolar. Foi denominado “Escola Major Custódio Pereira”, em homenagem póstuma ao Exmo Sr. Major Custódio Pereira, um dos ilustres homens de nossa terra, o qual passou por elevados postos como: Inspetor de Ensino Primário, Escrivão, Juiz de Paz e outros.
Em 1962, porém, sob o auspicioso governo do Exmo Senhor José de Magalhães Pinto, recebeu o distrito por disposição da Lei Estadual 2.764 de 30 de dezembro de 1962, veio assegurar-lhes as prerrogativas do individualismo municipal, desmembrando de Patrocínio. Pela Lei Estadual nº 2.764 de 30/12/1962, o distrito foi elevado à categoria de Município, composto da sede de Cruzeiro da Fortaleza e do distrito de Brejo Bonito, integrando um só todo na geografia municipal. No município de Cruzeiro da Fortaleza, a instalação de seu primeiro governo deu-se em 01/03/1963, e seu primeiro administrador foi o Sr. José Ferreira da Silva, designado Intendente por seis meses, até que se elegesse o primeiro Prefeito. A emancipação política de Cruzeiro da Fortaleza deu-se no dia 1º de Março de 1962, com seu único distrito, Brejo Bonito. Era governador do Estado de Minas Gerais, o Senhor José de Magalhães Pinto. A cada ano, no dia 1º de Março, comemora-se o “Dia do Município”. Foi intendente no município durante 6 meses, o Sr. José Ferreira da Silva.
