Jens Nicolai Olsen blev født i Gærum udenfor Frederikshavn i 1841. Han flyttede til byen i 1863, og etablerede sit eget skibsværft i 1882.

Det var Nicolai Olsen der byggede det første Danske skruedrevene fiskefartøj. Det var i 1891, og hun sejler stadig under sit oprindelige navn W. Klitgaard. I dag sejler hun dog ikke med fisk, men med museumsgæster.

Det var ikke nødvendigt for Nicolai Olsen at konkurrere med H.V. Buhl. Skibsbyggerierne kunne afsætte alt hvad de byggede til de mange fiskere, som omlagde fiskeriet fra de åbne sejljoller til dæksbåde.

Værftet lå på den forkerte side af havnepladsen, på hjørnet af Tordenskioldsgade. Når bådene skulle søsættes måtte de derfor trækkes tværs over havnepladsen. Til reparationer brugte værftet den gamle ophalerbedding i gammelhavn.

Skibsværftet blev overtaget af Hjørne & Jacobsen i 1915 og igen af B&W Alpha Diesel i 1944. Med byggeriet af den nye Fiskerihavn omkring 1956, flyttede værftet til sin nuværende plads.