Terytorium obecnej archidiecezji było częścią Prefektury Apostolskiej Stanów Zjednoczonych Ameryki, powstałej 26 listopada 1784, która to 6 listopada 1789 została podniesiona do rangi diecezji ze stolicą w Baltimore.
Pierwszym katolickim kościołem w Nowym Jorku był kościół św. Piotra przy Barclay Street. Plac został zakupiony od Trinity Episcopal Church i sfinansowany przez hiszpańskiego konsula.
W związku z tym, że pierwszy mianowany biskup nie mógł odpłynąć z Włoch, ze względu na blokadę napoleońską, administratorem został mianowany ks. Kohlman. Przypisuje mu się zorganizowanie diecezji i przygotowanie do budowy katedry św. Patryka przy Mulberry St. Wśród trudności na jakie w tym czasie napotykali katolicy był antykatolicki fanatyzm w szkolnictwie Nowego Jorku. Silne ruchy natywistyczne starały się trzymać katolików z dala od kraju i zapobiegać ich rozwojowi.
23 kwietnia 1847 z terytorium diecezji wyodrębniono diecezje Albany i Buffalo, a 19 lipca 1850 diecezja została podniesiona do rangi archidiecezji. 29 lipca 1853 ponownie wyodrębniono kolejne diecezje Newark w New Jersey i Brooklyn.
Św. Elżbieta (Elizabeth Ann Seton) – znana również jako Matka Seton, założycielka Zakonu Sióstr Miłosierdzia, pierwsza święta kanonizowana w Nowym Jorku. Pierwsza, urodzona w Stanach Zjednoczonych, kanonizowana na świętą. Ciotka biskupa James Roosevelt Bayley (pierwszego biskupa Newark, New Jersey, a ósmego arcybiskupa Baltimore).
Św. Franciszka (Frances Xavier Cabrini) – znana również jako Matka Cabrini, założycielka Zakonu Sióstr Misjonarek Najświętszego Serca Pana Jezusa.
Św. Izaak Jogues – jezuickimisjonarz, aktywny na północy stanu Nowy Jork, ale przed utworzeniem diecezji w Nowym Jorku.
Św. Jan Nepomucen Neumann – przyjął święcenia kapłańskie w Nowym Jorku, później wstąpił do Redemptorystów. Był czwartym biskupem Filadelfii (1852/60), a pierwszym, kanonizowanym biskupem Stanów Zjednoczonych. Jako biskup Filadelfii, założył pierwszy, katolicki, diecezjalny szkolny system w Stanach Zjednoczonych.