Vitorino fue el tercero de los cinco hermanos Salomé, todos músicos, siendo los más conocidos Janita Salomé y él. Muy joven aún hizo amistad con Zeca Afonso durante el servicio militar de ambos en el Algarve. Se trasladó a Lisboa con 20 años, viviendo la bohemia lisboeta más que sus estudios de Bellas Artes, iniciados en 1968. Emigró a Francia, y fue en Paris donde comenzó a alternar con otros músicos emigrados como Sérgio Godinho o José Mário Branco, llegando a participar en la grabación de varios álbumes de José Afonso] (Coro dos Tribunais) y Fausto.

En marzo de 1974 participó en el Primer Encuentro de la Canción Portuguesa, celebrado en el Coliseu dos Recreios. Poco después apareció su primer sencillo Morra Quem Não Tem Amores, que encabezaría su primer álbum de canciones tradicionales portuguesas, publicado en 1975. En 1988, su álbum Negro Fado fue merecedor del Prémio José Afonso (galardón que volvería a recibir en 1992 con Eu Que Me Comovo Por Tudo E Por Nada). Dos años después se asoció con el cuarteto Lua Extravagante, con Filipa Pais y sus hermanos Janita y Carlos Salomé.

El 9 de junio de 1994 fue investido Oficial da Ordem da Liberdade.^[2]​ En la Expo-98 participó en los espectáculos “A Utopia e a Música” con el repertorio menos conocido de Zeca Afonso.

Ha participado en muy diversos proyectos musicales y culturales con artistas de Brasil, Cuba, y otros países, entre los que cabe mencionar por ejemplo la campaña Uma Escola Para Timor para recuperar el sistema educativo timorense, a lo largo de 2000.

• Preto no Branco
• Arma Branca
• Viva La Vida
• Vila Velha

• Estação da Minha Vida

• Semear Salsa ao Reguinho (LP, Orfeu, 1975) coproducido por Fausto Bordalo Dias
• Se fores ao Alentejo
• Semear salsa ao reguinho
• Cantiga dum marginal do séc.XIX
• A Primavera do Outono
• Ó patrão dê-me um cigarro
• São saias, senhor, são saias
• Dizem p'ra 'í que chegou
• Cantiga de uma greve de Verão
• Temos a força dos ventos
• O tudo é todo nosso
• Menina estás à janela
• Morra quem não tem amores
• Vou-me embora vou partir
• Os Malteses (LP, Orfeu, 1977)
• Alentejo és nossa terra
• Rouxinol repenica o cante
• Oh Beja, terrível Beja
• Barrancos és minha terra
• Saias da União Cooperativa do Redondo
• O maltês
• Cantares do mês d' Outubro
• Fui colher uma romã
• Marcha da patuleia
• Chamaste-me extravagante
• Maio
• Lindo ramo verde escuro
• Não Há Terra Que Resista - Contraponto (LP, Orfeu, 1979)
• Delicada da cintura
• Não há terra que resista
• Litania para um amor ausente
• Contos do príncipe real
• Maria dos mil sorrisos
• Maria da Fonte
• Dá-me cá os braços teus
• Porque me não vês Joana
• Quadras soltas (de embalar)
• Viva a rainha do sul
• Diz a laranja ao limão
• Sedas a vento
• Romances (LP, Orfeu, 1981)
• Catrapiado
• Laurinda
• Dona Filomena
• Bela Nau Catarineta
• Eu hei-de amar uma pedra
• Em 25 de Março
• Senhora Maria
• Levantar ferros
• Mana Isabel
• Sospirastes baldovinos
• Indo eu por 'í abaixo
• Oh! que janela tão alta
• Flor de La Mar (LP, EMI, 1983)
• Leitaria Garrett (LP, EMI, 1984)
• Abertura
• Saias da vila do Redondo
• Menina estás à janela
• Postal para D.João III (a Zeca Afonso)
• Cantiga partindo-se
• Poema
• Ai os modos de ser lágrima
• Confissões (Nunca fui além)
• Leitaria Garrett
• Andando pela vida
• Tragédia da rua das Gáveas
• Tinta verde
• Carbonárias (final)
• Sul (LP, EMI, 1985)
• Negro Fado (LP, EMI, 1988) PJA
• Cantigas de Encantar (Casete, EMI, 1989)
• Eu Que Me Comovo Por Tudo e Por Nada (CD, EMI, 1992) PJA
• As Mais Bonitas (Compilação, EMI, 1993)
• A Canção do Bandido (CD, EMI, 1995) CAND PJA
• Fado alexandrino
• Tocador da concertina
• Fado triste
• Fado da prostituta da rua S. António da Glória
• Nasci para morrer contigo
• Fado do pedinte da Igreja dos Mártires
• Cruel vento
• Fado Isabel
• Veste de noite este quarto
• Fado da pré-reforma
• Rigoroso do pescador da marginal
• Fado do jovem velho
• Os nomes do amor
• La Habana 99 (CD, EMI, 1999) with Septeto Habanero
• Alentejanas e Amorosas (CD, EMI, 2001)
• As Mais Bonitas 2 - Ao Alcançe da Mão (Compilation, EMI, 2002)
• Utopia (CD, EMI, 2004) with Janita Salomé
• Ninguém Nos Ganha Aos Matraquilhos! (CD, EMI, 2004)
• Tudo (Compilation, EMI, 2006)
• Abril, Abrilzinho (CD, Público/Praça das Flores, 2006)
• Ao Vivo- Vitorino a preto e branco (CD, Magic Music/Vitorino, 2007)
• Tango (CD, Magic Music/Vitorino, 2009)
• Viva a República (CD de dois originais, comemoração centenário implantação da República, Diário de Notícias/Montepio, 2010)

• Queda do Império - Colecção Caravela (EMI, 1997)
• O Melhor dos Melhores n.º 43 (Movieplay, 1996)
• Clássicos da Renascença n.º 84 (Movieplay, 2000)
• Menina Estás À Janela - Colecção Caravelas (EMI, 2004)
• Grandes Êxitos (EMI, 2006)

•   Wikimedia Commons alberga una categoría multimedia sobre Vitorino.
• Sitio del cantor