Este trabalho investiga a qualidade do Ensino Fundamental das capitais brasileiras no período de 1996 a 2005 face às mudanças expressivas que ocorreram na educação no Brasil, principalmente no que se refere à alteração no fluxo escolar, ao papel dos municípios na administração e ao modo heterogêneo pelo qual cada um destes fatores atuou nas diferentes redes de ensino das capitais. Inicialmente, o estudo analisa a evolução de três indicadores de qualidade do Ensino Fundamental - desempenho escolar, taxa de não aprovação e taxa de distorção idade série - das redes de ensino estaduais e municipais das capitais brasileiras, bem como o mapeamento das políticas educacionais implementadas pelos governos no período analisado. Em seguida, investigou-se a associação das políticas públicas sobre o desempenho das redes de ensino das capitais brasileiras, a partir dos dados para a 4ª série do Ensino Fundamental do SAEB 1999, 2001 e 2003. O resultado da estimação do modelo multinível mostrou que as políticas relacionadas ao processo de escolha dos diretores, à formação dos professores, ao atendimento à Educação Infantil têm associação positiva no desempenho discente. O trabalho também investiga, a partir do desempenho da coorte etária de 10 anos, a qualidade da educação considerando tanto o desempenho dos alunos quanto o fluxo escolar. Os resultados indicam, para o Brasil, queda de 7,5 pontos entre 1995 e 2003. Para as capitais brasileiras, o cenário para o período 1999 a 2003 é de estabilidade. Conseqüências para as políticas públicas na área de educação são discutidas.