Fils d’un agent de la GRC, il a passé une grande partie de son enfance dans la communauté de Fort Norman, aujourd’hui Tulita, dans les Territoires du Nord-Ouest. Lorsque Nielsen avait quatre ans, la famille a voyagé vers le sud pour que son frère aîné Eric, qui a plus tard été chef du gouvernement du Territoire du Yukon et vice-premier ministre en tant que député conservateur, puisse aller à l’école à Edmonton. Nielsen s’est engagé comme mitrailleur aérien dans l’ARC à la fin de son adolescence.
Après la Seconde Guerre mondiale, Nielsen s’installe à Calgary et fait ses débuts dans le monde du spectacle dans une station de radio locale en tant qu’ingénieur radio, annonceur et DJ. Désireux d’étudier la comédie, Nielsen s’installe à Toronto pour suivre les cours de l’Académie des arts radiophoniques de Lorne Greene, puis obtient une bourse pour la célèbre Neighbourhood Playhouse de New York. Sanford Meisner lui a appris à jouer la comédie, Martha Graham lui a appris à danser, il a perfectionné ses compétences au légendaire Actors’ Studio, et les actions d’été ont payé les factures.
En 1950, Nielsen fait ses débuts à la télévision dans la prestigieuse série anthologique Studio One, jouant aux côtés d’un autre nouveau venu, Charlton Heston. Rien que cette année-là, il est apparu dans 46 programmes télévisés en direct. Hollywood lui fait signe en 1954, et Nielsen lance sa carrière cinématographique en jouant le rôle principal dans The Vagabond King (1956). Il a ensuite joué dans Planète interdite, Tammy And The Bachelor, The Poseidon Adventure, Peyton Place, Bracken’s World et Due South.
En cours de route, il a trouvé le temps de jouer en tant qu’invité dans presque toutes les séries dramatiques à succès, y compris The Untouchables, Alfred Hitchcock Presents, Ben Casey, Dr. Kildare, Bonanza, The Man From U.N.C.L.E., Hawaii 5-0, The Streets Of San Francisco, Ironside, Kojak, M*A*S*H, The Golden Girls et bien d’autres encore.
Dans les années 1980, Nielson a joué le rôle du lieutenant Frank Drebin dans Airplane, et une toute nouvelle génération de fans a découvert son timing comique impeccable. La superstar nommée aux Emmy Awards a reçu de nombreuses récompenses, la plus importante étant le Jack Benny Award de l’UCLA en 1995, un prix réservé aux meilleurs et aux plus brillants noms de la comédie.
