Nicolaj Stochholm er født i Charlottenlund nord for København i 1966, og er vokset op i København, hvor han også bor i dag. I mellemtiden har han boet i kortere og længere perioder udenfor Danmark, bl.a. i Irland, Spanien og Marokko.
Stochholm startede med at skrive digte i 1980’erne. Han fik sine første digte trykt i tidsskriftet Hvedekorn i 1984, og på en måde var det mere punken og guitaren, der drev værket i de år. Om i udgangspunktet at være musiker frem for digter siger Stochholm i et interview mange år senere med Kim Skotte: ”Næ, men dengang spillede jeg også rockmusik, og jeg læste ikke 80’er-digterne, for jeg var bange for at blive påvirket for meget. Så jeg læste Eliot, Lorca og Rimbaud. Det var bøger, og det skulle ikke blandes sammen!” (Kim Skotte: Fra digter til musiker – Rockmonsteret kommer op af lagunen. Politiken, 2014-01-25).
Stochholm identificerer sig ikke med og klassificeres heller ikke som en 1980’er-digter, men sporene derfra er tydelige. Måske bl.a. derfor er han faldet lidt imellem generationerne i den med brede penselstrøg malede litteraturhistorie, hvor han hverken passer helt ind i 1980’ernes alvorstunge og melankolske poesi eller i 1990’ernes mere ironiske og minimalistiske tradition. Alligevel fornægter den store patos sig ikke i Stochholms poesi.
På tværs af forfatterskabet findes et stort arbejde med og kærlighed til det musikalske udtryk. Om forbindelsen mellem musikken og digtningen som udtryksform siger Stochholm: ”Der er en forbindelse i åndedraget, rytmen, anslaget.” (Kim Skotte: Fra digter til musiker – Rockmonsteret kommer op af lagunen. Politiken, 2014-01-25). Stochholms linjer synes hele tiden som skabt af en rytmisk forkærlighed i sproget. Selvom guitaren var lagt væk i mange år, er det da også i anledning af en ny plade med bandet, Stochholm spiller i, The Liquid, at det citerede interview blev bragt i avisen.
Nicolaj Stochholm bor i dag på Nørrebro, og i 2018 udkom hans 11. bog ”Udenfor pesthospitalet”.