Em 1996, se afasta de Zambiasi e abandona o PTB, ingressando no PDT. Por esta legenda se candidata ao governo do estado do Rio Grande do Sul em 1998. Fica em terceiro lugar e apoia Olívio Dutra do PT, que ganha as eleições no segundo turno. O PDT entra no governo mas, após um ano, decide abandonar a administração estadual. Emília Fernandes, entre outros pedetistas, como Sereno Chaise e Dilma Rousseff, decide não seguir o partido e acaba se filiando no PT.
No PT, torna-se a primeira mulher a presidir uma Comissão Permanente do Senado, a de Infra-Estrutura, entre os anos de 1999 e 2000. Foi vice-líder do partido no Senado, coordenou a bancada federal gaúcha do PT e foi uma das coordenadoras da Bancada Feminina do Congresso Nacional, além de presidir o Conselho Parlamentar para o Diploma Mulher Cidadã Bertha Lutz.
Em 2002, se candidatou à reeleição, mas não é reconduzida ao Senado. Os eleitos foram Zambiasi (PTB), seu antigo padrinho, e o companheiro de partido Paulo Paim.
Com a eleição de Luiz Inácio Lula da Silva, Emília é indicada em 2003, para a Secretária Especial de Políticas para as Mulheres, com status de ministra. Pertenceu ao grupo de petistas derrotados nas urnas que foram recompensados com cargos na esfera federal, como os gaúchos Tarso Genro e Miguel Rossetto. Entretanto, um ano após tomar posse, foi substituída na pasta por Nilcéa Freire.
Em 2006, candidatou-se a deputada federal, obtendo a suplência. Em 2009, em função da morte do deputado federalAdão Pretto, Emília assumiu em 17 de fevereiro uma cadeira na Câmara dos Deputados, como primeira suplente do PT. Nas eleições de 2010, concorreu novamente deputada federal, e como em 2006, obteve a suplência.
Em 2013, Emília Fernandes ingressou no PCdoB, partido pelo qual pretendia disputar uma vaga ao Senado em 2014, porém, um acordo entre PT, PTB e PCdoB decidiu por lançar o ex-governador Olivio Dutra como candidato.[2] Ela foi candidata a deputada estadual,mas não foi eleita.