He trained as an engine-room seaman and left Jamaica for Britain in 1939, before serving in World War II.
While there, he joined Ghanaian music troupes (playing with E. T. Mensah and Guy Warren) and tried to establish a timber business.
When that failed, he returned to Britain and began performing with his brother Noel, working their way to the Gateways, a pioneering lesbian club in Chelsea, where he met the pianist Chester Harriott.
The pair formed a duo, with Harriott on the piano and Brown singing (he was a tenor), an arrangement that proved successful; they spent eight years playing and touring as a variety act, Harriott & Evans (for Victor Brown was then known on stage as Vic Evans), mixing with a booming jazz scene and travelling across the world.
As support act for a Tommy Steele concert at the Blackpool Opera House in August 1961, they were described as "Europe's greatest coloured entertainers".