ヨーロッパ人入植者が移住してくる以前は、現在のハーレム・エリアにはManhattans (Manhattos) と呼ばれる部族などのネイティブ・アメリカン部族が住んでいた。おそらく彼らのほとんどはレナペ族で[5]、半遊牧民的な生活を営んでいた。ハーレムの平地では何百人もの人々が農作をしていた[6]。1637-1639年には、ヨーロッパ人による最初の入植が確立された。1637年に、最初のヨーロッパ人(オランダ人移民のHendrick (Henry) de Forest, Isaac de Forest、およびRachel de Forest)がこの地区に住み着いた[5]。1639年にはen:Jochem Pietersen KuyterがZedendaalまたはBlessed Valleyと呼ばれる農園を、ハーレム川沿いの現在の127丁目から140丁目の間に開拓した[7][8]。
1664年に、イギリスがニューネーデルランドの支配権を取得し、ニューヨーク植民地総督リチャード・ニコルズはニュー・ハーレム(後のハーレム村, village of Harlem)の南端の境界線として現在のイースト川と74丁目の位置から西に伸びる"Harlem Line"を定めた[14][15][16][17]。イギリスはこの地区の名前を"ランカスター" (Lancaster) に変更しようと目論んだが定着せず[18]、最終的にはオランダ語のHaarlemが英語化してHarlemという現在の名称に落ち着いた。オランダは1673年に一年だけニューヨークの支配権を取り戻している[19]。ハーレム村はゆっくりと発展し、18世紀半ば頃にはニューヨーク市の裕福な人たちの保養地となった[20]。この当時の建物はモリス=ジュメル・マンション (en) しか現存していない。
Pierce, Carl Horton, et al. New Harlem Past and Present: the Story of an Amazing Civic Wrong, Now at Last to be Righted. New York: New Harlem Pub. Co., 1903.