Issu d'une famille modeste d'origine danoise, Niels Arestrup grandit en banlieue parisienne et s'inscrit après le lycée au cours de Tania Balachova. Il débute sa carrière au théâtre avant d'apparaître pour la première fois au cinéma dans Miss O'Gynie et les hommes fleurs de Samy Pavel en 1973, puis dans Stavisky d'Alain Resnais en 1974.
Sans jamais abandonner le théâtre, il se construit une carrière atypique faite de seconds rôles de salauds (Les Loups entre eux, 1985 ; La Rumba, 1986) et de personnages ambigüs (La Dérobade ou La Femme flic aux côtés de Miou-Miou). A partir du milieu des années 80, on le voit s'imposer en tête d'affiche de quelques longs métrages comme Le Futur est femme (1984) de Marco Ferreri, où il devient l'amant d'un couple à trois, La Tentation de Venus (1991), où il joue un chef d'orchestre hongrois aux prises avec l'Opéra de Paris, Le Pique-nique de Lulu Kreutz (1999), où il incarne un violoncelliste célèbre et malheureux, ou encore Parlez-moi d'amour (2002), première réalisation de Sophie Marceau où il interprète un mari vieilissant qui se sépare de sa femme.
En 2005 et 2009, Niels Arestrup trouve deux de ses rôles les plus forts en tournant pour Jacques Audiard : on le voit ainsi camper le père, agent immobilier peu scrupuleux, de Romain Duris dans De battre, mon coeur s'est arrêté, prestation qui lui vaut le César du Meilleur second rôle masculin en 2006, et un terrifiant parrain de la pègre corse dans Un prophète, Grand Prix au Festival de Cannes 2009. Entre-temps, il s'essaie pour la première fois à la réalisation en dirigeant en 2006 Yvan Attal dans un drame politique intitulé Le Candidat.