É nomeado, em julho de 1556, governador geral. Em dezembro do ano seguinte chega à Bahia, sede do governo geral. Sua primeira providência é estabelecer a harmonia na colônia, abalada por desavenças entre colonos e jesuítas. Cuida também de acalmar os índios hostis, contando para isso com a ajuda dos padres Manuel da Nóbrega e José de Anchieta.
Em 1560 ataca os franceses estabelecidos na Baía de Guanabara, mas só consegue afugentá-los para o interior. Retorna à Guanabara em 1567, em socorro ao sobrinho, Estácio de Sá, que fora mandado para combater os invasores. Estácio havia fortificado o litoral, lançando as bases da cidade de São Sebastião do Rio de Janeiro.
Juntando forças, os dois expulsam os franceses. Mem de Sá morre em Salvador, já desejoso de deixar o governo geral para voltar para Portugal.