To understand what factors control species colonization and extirpation within specific paleoecosystems, we analyzed radiocarbon dates of megafaunal mammal species from New York State after the Last Glacial Maximum. We hypothesized that the timing of colonization and extirpation were both driven by access to preferred habitat types. Bayesian calibration of a database of 39 radiocarbon dates shows that caribou (Rangifer tarandus) were the first colonizers, then mammoth (Mammuthus sp.), and finally American mastodon (Mammut americanum). The timing of colonization cannot reject the hypothesis that colonizing megafauna tracked preferred habitats, as caribou and mammoth arrived when tundra was present, while mastodon arrived after boreal forest was prominent in the state. The timing of caribou colonization implies that ecosystems were developed in the state prior to 16,000\ cal\ yr BP. The contemporaneous arrival of American mastodon with Sporormiella spore decline suggests the dung fungus spore is not an adequate indicator of American mastodon population size. The pattern in the timing of extirpation is opposite to that of colonization. The lack of environmental changes suspected to be ecologically detrimental to American mastodon and mammoth coupled with the arrival of humans shortly before extirpation suggests an anthropogenic cause in the loss of the analyzed species.