Przed przybyciem Europejczyków obszary te zamieszkiwali Indianie Mohegan, i Delawarowie (grupa algonkińska) oraz Mohawk, Oneidowie, , i Seneka (z Ligi Irokezów). Pierwszym Europejczykiem który odwiedził terytorium przyszłego Nowego Jorku był Giovanni da Verrazzano w 1524. Henry Hudson w 1609 odkrył główną rzekę stanu, później nazwaną jego nazwiskiem.
Pierwszymi stałymi europejskimi osadnikami byli Holendrzy, którzy od 1613 roku organizowali w okolicach Manhattanu prywatne terytorium zamorskie i po zasiedleniu go przez pierwszą grupę emigrantów w 1624 przekształcili je w holenderską prowincję o nazwie Nowe Niderlandy. Rok później założono tam Fort Amsterdam (późniejszy Nowy Amsterdam, a od 1665 Nowy Jork). W 1664 kolonię zajęli bez oporu Anglicy z sąsiedniej Nowej Anglii. Holendrzy odzyskali ją przejściowo w roku 1673, znów przemianowując Nowy Jork (nazwany tak na cześć brata króla angielskiego, księcia Jorku) na Nową Oranię (nid. Nieuwe Oranje). Jednak już rok później, po III wojnie angielsko-holenderskiej, zrzekli się całej kolonii na rzecz Anglików, którzy przemianowali ją na Prowincję Nowy Jork (istniejącą do 1777).