Nielsen began his performing career on stage as a dancer, including the musicals Call Me Madam and West Side Story. He entered film in the sixties, with bits as dancers, and had a larger supporting role in a trio of seventies comedies about women entering military service (a sergeant in Piger i trøjen and Piger i trøjen 2, switched to naval lieutenant in Piger til søs). He appeared in the Oscar-winning film Babette's Feast as the grocer and had small roles in the Swedish film Smugglarkungen (as a Danish smuggler) and the Norwegian Deilig er fjorden (with Sverre Holm). On Danish television, he appeared in several Christmas serials (notably as Skipper in 1989's Nissebanden i Grønland, frequently rerun since) and in two episodes each of the drama Matador (as the bicycle dealer) and Lars Von Trier's Riget.
Nilsen's cartoon dubbing credits include Darkwing Duck, Hotel Transylvania 2 and 3 (Vlad), and Cars 3 (Smokey). In live-action, he dubbed Dick Van Dyke in Night at the Museum, Robert Redford in Pete's Dragon, Swedish actor Torsten Lilliecrona in the Saltkråkan movies and TV series of the 60s and 70s, and Norwegian actor Ivar Nørve in the Karsten og Petraseries and movies.