Mesto bolo založené Holanďanmi v roku 1624 ako obchodné stredisko New Amsterdam (hol. Nieuw-Amsterdam – Nový Amsterdam) a od roku 1790 je najväčším mestom Spojených štátov.
New York bol tiež prvým hlavným mestom Spojených štátov po prijatí ústavy.
Oblasť bola v čase objavu Európanmi v roku 1524 obývaná asi 5 000 indiánmi z kmeňa Lenape. Objaviteľom bol Giovanni da Verrazano, taliansky cestovateľ v službách francúzskej koruny, ktorý miesto nazval Nouvelle Angouleme.Prvú európsku osadu pod názvom Nieuw Amsterdam založili Holanďania na južnom cípe Manhattanu v roku 1614 s cieľom obchodovať s kožušinami. Vodca holandských kolónií Peter Minuit kúpil Manhattan od kmeňa Lenape v roku 1626 za 60 guldenov (dnes už vyvrátená legenda hovorí, že Manhattan bol kúpený za sklenené koráliky v hodnote 24 dolárov).V roku 1664 dobyli mesto Angličania a premenovali ho na New York na počesť Jakuba II., kniežaťa z Yorku a Albany.Na konci druhej anglo-holandskej vojny získali Holanďania kontrolu nad indonézskym ostrovom Run, ktorý bol v tej dobe oveľa významnejší, a Angličania si ako výmenu mohli ponechať kontrolu nad New Yorkom. Do roku 1700 klesla populácia kmeňa Lenape na 200 osôb.