Nielsen was born on 11 February 1926 in Regina, Saskatchewan. His mother, Mabel Elizabeth (née Davies), was an immigrant from Wales, and his father, Ingvard Eversen Nielsen, was a Danish-born constable in the Royal Canadian Mounted Police. Nielsen had two brothers; the elder, Erik Nielsen (1924–2008), was a long-time Canadian Member of Parliament, cabinet minister, and Deputy Prime Minister of Canada from 1984 to 1986.
Nielsen's half-uncle Jean Hersholt
(pictured here in the 1936 film His Brother's Wife
) inspired him to become an actor.
Nielsen's half-uncle Jean Hersholt was an actor known for his portrayal of Dr. Christian in a radio series of that name, and the subsequent television series and films. In a 1994 Boston Globe article, Nielsen explained, "I did learn very early that when I would mention my uncle, people would look at me as if I were the biggest liar in the world. Then I would take them home and show them 8-by-10 glossies, and things changed quite drastically. So I began to think that maybe this acting business was not a bad idea, much as I was very shy about it and certainly without courage regarding it. My uncle died not too long after I was in a position to know him. I regret that I had not a chance to know him better."
Nielsen lived for several years in Fort Norman (now Tulita) in the Northwest Territories, where his father was with the Royal Canadian Mounted Police. His father was an abusive man who beat his wife and sons, and Leslie longed to escape. When he graduated from high school at 17, he joined the Royal Canadian Air Force, though he was legally deaf (he wore hearing aids most of his life). Following graduation from Victoria School of the Arts in Edmonton, Nielsen enlisted in the Royal Canadian Air Force and trained as an aerial gunner during World War II. He was too young to be fully trained or sent overseas. He worked briefly as a disc jockey at a Calgary, Alberta, radio station, before enrolling at the Lorne Greene Academy of Radio Arts in Toronto. While studying in Toronto, Nielsen received a scholarship to the Neighborhood Playhouse. He noted, "I couldn't refuse, but I must say when you come from the land of the snow goose, the moose, and wool to New York, you're bringing every ton of hayseed and country bumpkin that you packed. As long as I didn't open my mouth, I felt a certain security. But I always thought I was going to be unmasked: 'OK, pack your stuff.' 'Well, what's the matter?' 'We've discovered you have no talent; we're shipping you back to Canada.'" He moved to New York City for his scholarship, studying theatre and music at the Neighborhood Playhouse, while performing in summer stock theatre. Afterward, he attended the Actors Studio, until his first television appearance in 1950 on an episode of Studio One, alongside Charlton Heston, for which he was paid $75.