Oblast byla v době objevu Evropany v roce 1524 obydlena asi 5000 indiány z kmene Lenapů. Objevitelem oblasti byl Giovanni da Verrazzano, italský cestovatel ve službách francouzské koruny, který místo nazval Nové Angouleme (Nouvelle Angouleme). První evropskou osadu pod názvem Nový Amsterdam (Nieuw Amsterdam) založili Nizozemci na jižním cípu Manhattanu v roce 1614 za účelem obchodu s kožešinami. Vůdce nizozemských kolonií Peter Minuit koupil Manhattan od kmene Lenape v roce 1626 za 60 guldenů (dnes již vyvrácená legenda říká, že Manhattan byl koupen za skleněné korálky v hodnotě 24 dolarů). V roce 1664 dobyli město Angličané a přejmenovali je na New York na počest pozdějšího krále Jakuba II., tehdy vévody z Yorku a Albany. Na konci druhé anglo-nizozemské války získali Nizozemci kontrolu nad indonéským ostrovem Run, který byl v té době pro ně mnohem významnější, a Angličané si výměnou mohli ponechat kontrolu nad New Yorkem. Do roku 1700 klesla populace kmene Lenape na 200 osob.

Význam New Yorku jako přístavu pod britskou vládou rostl. V roce 1754 byla chartou vydanou Jiřím II. založena na dolním Manhattanu Columbijská univerzita, v té době pod jménem Kings's College. Během Americké války za nezávislost se ve městě odehrála série bitev známých pod názvem Newyorská kampaň. V roce 1789 se v New Yorku sešel Kongres a první prezident George Washington byl inaugurován v budově Federal Hall na Wall Street.