Its previous name was Contrasta (‘the one in front’) and it changed its name to improve it (Valença stands for ‘valiant’). It received its present name in 1262 by order of King Afonso III of Portugal. The toponymic complement do Minho is added to distinguish it from other Valença. Cfr. DOELP (s. v. Valença).

Cited bibliography: 

-DOELP = Machado, José Pedro. Dicionário onomástico etimológico da língua portuguesa. Lisboa: Livros Horizonte, 2003, 3ª ed.