Nyu-York shahrining dastlabki yozma tarixi 1524-yilda birinchi yevropalik sayohatchi Giovanni da Verrazzano bilan boshlanadi. Hududga yevropaliklarning kelib o'rnashishi 1608-yilda Gollandiya koloniyasi bilan boshlanadi va Yangi Amsterdam shahriga 1624-yilda asos solinadi.

"Ozodlik o'g'lonlari" tashkiloti Britaniya hokimiyatiga qarshi harakatlarni Nyu-Yorkdan turib olib borgan va 1765-yilda shu shaharda Tamg'a akti kongressi vakillari o'n uch mustamlakalarning barchasidan yig'ilib, qirollik siyosatiga qarshi harakatni uyushtirishga harakat boshlangan. Shaharning strategik joylashuvi va yirik dengiz porti sifatidagi maqomi tufayli Britaniya Nyu-Yorkni 1776-yilda bosib olgan. General George Washington bir qator janglarda magʻlub bo'lib, chekinishga majbur bo'lgan (istisno sifatida Harlem Heights jangini aytish mumkin va bu jangdagi g'alaba Washingtonning urushdagi birinchi g'alabasi edi). Britaniya armiyasi shaharni egallab, 1873-yilgacha shahar Britaniyaning Shimoliy Amerikadagi harakatlari uchun operativ nuqta sifatida xizmat qilgan va bu shaharga barcha mustamlakalardan loyalistlarning (Shimoliy Amerikada qirollik hokimiyati saqlanib qolishi tarafdorlari) oqib kelishiga sabab bo'lgan.

Shahar Konfederatsiya moddalariga ko'ra 1785-1789-yillar oralig'ida milliy poytaxt vazifasini bajargan va yangi AQSH Konstitutsiyasiga ko'ra ham 1789-1790-yillar oralig'ida qisqa muddatga davlat poytaxti hisoblangan. Shaharda AQSHning birinchi prezidenti George Washington o'zining muddatini boshlagan, AQSH Huquqlar to'g'risidagi Bill shu shaharda qabul qilingan va birinchi AQSH Oliy Sudi shu shaharda o'z ishini boshlagan. Erie kanalining ochilishi upstate (tog'li, shimoliy) Nyu-York va Buyuk ko'llar mintaqalarining paroxodlar orqali shahar bilan bog'lanishiga sabab bo'lgan. Atlantika qirg'oqlari bo'ylab quyi Yangi Angliya bilan paroxodlar qatnovining yo'lga qo'yilishi bilan Nyu-York Atlantika okeanidagi eng muhim portga aylanadi.1840-1850-yillarda shimol va g'arbga tomon temir yo'llarning yotqizilishi bilan shaharning markaz sifatidagi ahamiyati yanada oshdi.

XIX asr boshlanishi bilan Yevropadan keluvchi immigrantlar oqimi shahar qiyofasini butkul o'zgartirib, tobora kengayib borayotgan sanoat uchun ishchi kuchi manbasi sifatida xizmat qildi. Bugungi Nyu-York shahri qiyofasi shakllanishiga 1898-yilda besh borolarning birlashtirilishi va Buyuk inqirozdan keyingi iqtisodiy va qurilish sohasining shiddat bilan o'sishi omillari muhim o'rin tutadi. Tarixi davomida Nyu-York ko'plab immigrantlar uchun asosiy AQSHga kirish porti hisoblangan va shaharning madaniy va iqtisodiy ta'siri sabab Nyu-York bugungi kunda Qo'shma Shtatlar va dunyodagi eng muhim nuqtalardan biridir.

Bugungi kunda Nyu-York shahri joylashgan hududda Lenape mahalliy amerikalik qabilalar istiqomat qilgan. Ushbu madaniy va lingvistik jihatdan bir-biri bilan qardosh bo'lgan mahalliy amerikaliklar Algonquin tilida so'zlashgan (hozirda Unami deb ataladi). Ilk Yevropalik kelgindilar ushbu Lenape qabilalarini ular yashovchi hudud nomlari bilan, masalan, Staten Island va New Jerseyda yashovchilarni "Raritan", Brooklyndagilarni "Canarsee" va Hudson daryosi bo'yida hamda quyi Manhattanda yashovchilarni "Hackensack" nomlari bilan atashgan.Ba'zi zamonaviy joy nomlari, misol uchun Raritan ko'rfazi yoki Canarsie Lenape tilidagi qabila nomlaridan olingan. Long Island orolining sharqiy qismida yashovchi qabilalar esa Yangi Angliyadagi Mohegan-Montauk-Narragansett tilida so'zlashuvchi Mohegan-Pequot qabilalari bilan yaqinroq bo'lgan.