Nicolai Nellemann blev født i 1892 i Saltofte på Fyn, men efter sin eksamen som landinspektør i 1913, blev han ansat i et landinspektørfirma i Nørresundby, og dette stod han i 1934 som eneejer af.
Hans familie havde længe ønsket en sommerhusgrund, og valget faldt på Sæby, fordi "her var flere solskinstimer end længere sydpå".
I 1925 erhvervede han 2 tdr. uopdyrket land, der bestod af en gammel grusgrav, et par mosehuller og en lyngbeklædt hedeskrænt, som i årene frem blev forvandlet til en sand naturperle.
I 1925 begyndte så landinspektør Nicolai Nellemann anlæggelsen af den nederste del af haven. Han begyndte i starten af 1950’erne og fortsatte op igennem 1960’erne anlæggelsen af paradisæblehaven oven for istids-skrænten. Nic. Nellemann stod selv for anlæggelse af haven, men havde igennem mange år fast ansat en gartner til at passe og fortsætte udbygningen.
I løbet af en årrække fik Nellemann samlet en enestående og unik samling af paradisæbler, idet de talte mere end 1000 træer, da der var flest.
Et familieforetagende
Nic. Nellemann fortsatte sit arbejde med haven frem til 1976, hvor han døde. Hans søn Ib Nellemann købte sine søskende ud af haven og fortsatte arbejdet og vedligeholdelses af haven frem til sin død i 1991.
Ib Nellemann lod i 1977 en fond oprette, som skulle gøre det muligt at fortsætte driften af haven efter hans død, og som skulle bevare den uforandret og åben for offentligheden.
Her var staudehave, rosenhave, georginer, drivhus og en stor samling af frugttræer og andre spændende træer, både nåletræer og løvtræer, som man også i dag kan glæde sig over.
Nic. Nellemann modtog i begyndelsen af 1940’erne Jydsk Haveselskabs vandrepokal for det smukkeste haveanlæg i Jylland 3 år i træk.
Nicolai Nellemanns store lidenskab var paradisæbletræer. I 1969 rummede haven ikke mindre end 100 ægte kinesiske sorter samt en række krydsninger, som Nic. Nellemann selv havde fremavlet. Han lavede også mange forsøg med frøplanter.
Nellemann havde et omfattende samarbejde med andre folk i Danmark omkring nye træer, men der blev også udvekslet podekviste. Specielle sorter blev fremskaffet fra udlandet, så han kunne udvide sin store samling. Han lavede et omfattende registreringsarbejde af sine mange træer frem til sin død i 1976.
Haven var en stor turistattraktion. Haven blev i begyndelse af 1970’erne overtaget af Nic. Nellemanns Fond, der stadig ejer haven. Sønnen Ib Nellemann fortsatte arbejdet i Haven frem til sin død i 1991.
I 1991 var der over 1000 paradisæbletræer (heraf 300-400 navngivne sorter).
Reetablering og genplantning
Nellemanns Haves Venner, der holdt stiftende generalforsamling den 19. juni 2006, gik derefter i gang med en omfattende reetablering. Efter et stort oprydnings arbejde, som begyndte i 2008 med udtynding flere steder i haven i samarbejde med Frederikshavn Kommune, kunne Nellemanns Haves Venner i foråret 2010 begynde en genplantning af Nic. Nellemanns egne kort og optegnelser fra anlæggelsen af den store paradisæblehave.
Der er plantet nye lærkehække og rosenbedet fra 1936 er blevet genskabt efter Nic. Nellemanns farveplan. Genplantningen af paradisæbletræer begyndte i september 2010 med 125 træer, i 2011 med 25 træer og i 2012 med 85 træer. “Det betyder at der igen er over 1000 paradistræer”, som Ib Nellemann skrev i 1991.
Desuden er der bygget madpakkehus og naturlegeplads. Lises pavillon er bygget i ny udgave oppe på skrænten med det gamle kobbertag, der stammer fra et brohus ved Limfjordsbroen.