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.
(pictured here in the 1936 film His Brother's Wife
) inspired him to become an actor.
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 Performing and Visual 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
 until his first television appearance in 1950 on an episode of
Studio One, alongside
 for which he was paid $75.