Verein

Stokholm begann seine Karriere 1996 bei Holbæk B&I. Von dort wechselte er 1998 zum damaligen Erstligisten AB Kopenhagen. In seiner ersten Saison für den Klub aus Gladsaxe machte er 22 Spiele und erzielte ein Tor. Mit AB gewann Nicolai Stokholm in seiner ersten Saison nach einem 2:1-Finalsieg gegen Aalborg BK zugleich auch den dänischen Pokalwettbewerb. In der Saison 1999/2000 machte Stokholm 30 Spiele und belegte mit AB Kopenhagen den dritten Platz. In der darauffolgenden Saison verlängerte er seinen Vertrag bis 2004 und kam in 24 Spielen zum Einsatz, in denen er fünf Treffer erzielte. Ein Jahr später um die gleiche Zeit hatte Nicolai Stokholm wie in der Saison 1999/2000 30 Einsätze vorzuweisen, anders als damals auch mit drei Torerfolgen. In der folgenden Saison hatte Nicolai Stokholm in Sachen Liga-Einsätze einen Einsatz mehr sowie fünf Torvorlagen vorzuweisen. Zur Saison 2003/04 ging Stokholm zu Odense BK. Stokholm kam in seiner ersten Saison in Odense auf 27 Punktspieleinsätze und drei Treffer. In der Folgesaison kam Stokholm in 31 Spielen zum Einsatz (vier Treffer). In der Saison 2005/06 spielte Stokholm auch 29 Mal und kam zu drei Toren.

Im Sommer zog es Stokholm ins Ausland. Er unterschrieb beim norwegischen Erstligisten Viking Stavanger. In Stavanger eroberte er sich schnell einen Stammplatz. So kam er in der zweiten Saisonhälfte der Tippeligaen, die im Frühling/Herbst-Modus läuft, auf 14 Einsätze, wo er zwei Tore erzielte. In der Saison 2007, seiner ersten kompletten Saison, kam er auf 24 Einsätze und erzielte vier Tore. In der Saison darauf kam er erneut zu 24 Einsätzen. Dieses Mal gelangen ihm fünf Treffer.

In der Winterpause der Saison 2008/09 kehrte Stokholm nach Dänemark zurück. Er unterschrieb beim FC Nordsjælland. In der zweiten Saisonhälfte kam er nur zu drei Einsätzen, wobei er in allen Spielen über 90 Minuten spielte. In seiner ersten ganzen Saison spielte Nicolai Stokholm in 30 Spielen und erzielte zwei Treffer. Zudem gewann er in der gleichen Saison auch erneut den dänischen Pokalwettbewerb. Beim 2:0-Finalsieg n. V. gegen den FC Midtjylland erzielte Nicolai Stokholm den Treffer zum 1:0. In der Folgesaison spielte Stokholm 25 Mal. Dabei gelangen ihm vier Tore. Zudem konnte im „Landspokalturneringen“ der Titel verteidigt werden, erneut durch einen Finalsieg über den FCM. Wiederum zwölf Monate später stand gar der Gewinn des dänischen Meistertitels.

Nach dem Karriereende 2014 war er ab 2020 als Vorstandsvorsitzender des Zweitligisten Holbæk B&I tätig.