Em 1953 nascia a Companhia Telefônica de Minas Gerais (CTMG), uma subsidiária da Companhia Telefônica Brasileira (CTB) em Minas Gerais, permanecendo assim até 1972. Nesta época, o controle acionário foi transferido para a Telebras, e a empresa se transformou em Telemig (Telecomunicações de Minas Gerais), uma subsidiária da Companhia Telefônica Brasileira (CTB).
No começo da década de 1990, a empresa deu início às operações de telefonia celular em Minas Gerais, com a tecnologia AMPS, por meio de uma subsidiária chamada Telemig Celular, exceto no Triângulo Mineiro.
Na mesma década, foi implementada a tecnologia TDMA. No início de 2004, anunciou que implantaria também a tecnologia GSM. Em setembro daquele mesmo ano, adquiriu licenças para implementar a tecnologia GSM no Triângulo Mineiro e Alto Paranaíba, que concentram as cidades situadas entre os rios Grande e Paranaíba, formadores do Rio Paraná.
No final de 2004, a tecnologia GSM foi implantada na sua área de atuação AMPS/TDMA. No primeiro semestre de 2005, foi anunciada sua entrada no Triângulo Mineiro. Dessa maneira, passou a oferecer a tecnologia GSM em todo o estado de Minas Gerais. No fim de 2007, a Telemig Celular foi a primeira operadora de todo o País a colocar em operação uma rede 3G, utilizando a tecnologia UMTS/HSDPA na faixa de 850 MHz, em Belo Horizonte.
Privatização e compra da Vivo
Em julho de 1998, ocorreu um processo de privatização da empresa Telemig, e a operadora foi desmembrada e leiloada à parte. A companhia de telecomunicações passou, por sua vez, a ser controlada pela Telpart, enquanto o braço da telefonia fixa se tornou parte do antigo consórcio Telemar – depois rebatizado como Oi, liderado pelo grupo Andrade Gutierrez. Enquanto isso, a Telemig Celular foi comprada por um consórcio liderado pelo Banco Opportunity. Posteriormente, em 2007, o controle acionário foi comprado pela operadora Vivo e totalmente absorvida em abril de 2008.
A marca Telemig Celular deixou de ser utilizada pouco após a sua compra pela operadora, desaparecendo completamente até o ano de 2010.
