Entretanto, essa situação favorável não foi duradoura. Exasperados pelas crueldades dos portugueses que, segundo a expressão de um dos seus historiadores, se mostraram mais bárbaras que os próprios bárbaros, os índios destruíram as plantações de seus inimigos, queimaram suas casas e massacraram todos aqueles que caíram em seu poder.

Para fugir aos seus ataques, os brancos abandonaram a cidade que haviam fundado e se retiraram para o lugar onde está hoje a Capital da província do Espírito Santo. Lá, ainda foram atacados pelos indígenas; mas, finalmente, conseguiram, por sua vez, uma grande vitória e, crendo deverem esse sucesso à intervenção da Virgem Maria, consagraram-lhe o novo estabelecimento, denominando-o Vila de Nossa Senhora da Vitória.

Nos combates que os portugueses travaram contra os índios, sucumbiram, sucessivamente, D. Jorge de Menezes e um outro nobre, também exilado, Simão de Castelo Branco, que assumira o governo da Colônia enquanto Coutinho, animado com seus primeiros êxitos, havia ido procurar novos auxílios em Portugal.

Fernão de Sá, filho de Mem de Sá, governador da Bahia, morreu, também, na guerra contra os índios da Capitania do Espírito Santo.