He was born Lamine Secka in Dakar, Senegal to a Wolof family, the youngest of five siblings; his Gambian father died shortly after his birth. When he was still young, his Senegalese mother sent him to live with an aunt in Georgetown (now Janjanbureh) in the Gambia, but he ran away to live on the streets in the capital, then known as Bathurst (now Banjul).
During the Second World War he found employment as an interpreter at an American air base in Dakar. He then worked on the docks. When he was 20, he stowed away on a ship to Marseilles, France, and lived for three years in Paris.
He arrived in London, England in 1952, and served for two years in the Royal Air Force, where he first received the nickname "Johnny", but then Bermudian actor Earl Cameron persuaded him to become an actor, and he attended RADA. He became a stagehand at the Royal Court Theatre, and appeared on stage in various plays from 1958.
He had a small part in the 1958 film version of Look Back in Anger, directed by Tony Richardson, who had seen him on stage. He took a leading role in the 1961 film Flame in the Streets, playing the Jamaican boyfriend of the (white) daughter (played by Sylvia Syms) of a liberal working-class trades unionist (played by John Mills). He also had a leading role in the 1961 film for ITV, The Big Pride, by Guyanese writer Jan Carew and Jamaican writer Sylvia Wynter. The film was set in then British Guiana; Sekka's character was a young prisoner who broke out with his older mentor.
In 1968, he also played the lead role in a West End production of Night of Fame. According to his obituary in The Times, this was the first time that a black actor had played a role written for a white man in English theatre. He was seen as a British equivalent to Sidney Poitier, and was frustrated that actors who started out at around the same time as him – such as Sean Connery, Terence Stamp, Michael Caine, Tom Courtenay and John Hurt – had become stars, and he had not.
