A Ferrovia Centro-Atlântica (FCA) iniciou suas atividades em 1º de setembro de 1996, após o processo de desestatização da malha da Rede Ferroviária Federal S.A. (RFFSA) e originou-se da fusão de três Superintendências:

• SR2, com sede em Belo Horizonte, originária Viação Férrea Centro-Oeste e parte da Estrada de Ferro Central do Brasil;
• SR8, com sede em Campos e originária da antiga Estrada de Ferro Leopoldina;
• SR7, com sede em Salvador e originária da antiga Viação Férrea Federal Leste Brasileiro.

A primeira etapa de transição RFFSA/FCA foi determinante para as transformações nos campos operacional, gerencial e de recursos humanos, delineando os primeiros moldes da nova ferrovia.

Originalmente a FCA foi consorciada pelos grupos Mineração Tacumã Ltda. (empresa controlada pela CVRD), Ralph Partners, Railtex International Holdings Inc, Interférrea S.A. – Serviços Ferroviários e Intermodais, Judori – Administração, Empreendimento e Participações S.A., Companhia Siderurgia Nacional (CSN), Gruçai Participações S.A., Tupinambarana S.A. e Varbra S.A., muitos dos quais vindos de grandes empresas nacionais e participação estrangeira. A concessão foi fixada em cerca de R$316 milhões.

Voltada exclusivamente para a operação ferroviária de cargas, a FCA passou a desenvolver sua logística focada, principalmente, em granéis como a soja, derivados de petróleo e álcool combustível.

A partir de agosto de 1999, a Companhia Vale do Rio Doce (CVRD) passou a ser líder do grupo de controle da Ferrovia Centro-Atlântica, fortalecendo o processo de gestão e recuperação da empresa.

Em setembro de 2003, autorizada pela Agência Nacional de Transportes Terrestres (ANTT), a Vale assumiu o controle acionário da FCA, com 99,9%.

Desde que assumiu a operação da malha Centro-Leste, a FCA tem colocado em prática um sólido plano de investimentos em recuperação da via permanente (linha férrea), aquisição/recuperação de locomotivas e vagões, melhorias tecnológicas e de segurança, meio ambiente e qualificação profissional. De 1997 até 2005, a empresa já investiu mais de R$2 bilhões.