Since their range expansion into eastern North America in the mid-1900s, coyotes (Canis latrans) have become the region’s top predator. Although widespread across the region, coyote adaptation to eastern forests and use of the broader landscape are not well understood. We studied the distribution and abundance of coyotes by collecting coyote feces from 54 sites across a diversity of landscapes in and around the Adirondacks of northern New York. We then genotyped feces with microsatellites and found a close correlation between the number of detected individuals and the total number of scats at a site. We created habitat models predicting coyote abundance using multi-scale vegetation and landscape data and ranked them with an information-theoretic model selection approach. These models allow us to reject the hypothesis that eastern forests are unsuitable habitat for coyotes as their abundance was positively correlated with forest cover and negatively correlated with measures of rural non-forest landscapes. However, measures of vegetation structure turned out to be better predictors of coyote abundance than generalized “forest vs. open” classification. The best supported models included those measures indicative of disturbed forest, especially more open canopies found in logged forests, and included natural edge habitats along water courses. These forest types are more productive than mature forests and presumably host more prey for coyotes. A second model with only variables that could be mapped across the region highlighted the lower density of coyotes in areas with high human settlement, as well as positive relationships with variables such as snowfall and lakes that may relate to increased numbers and vulnerability of deer. The resulting map predicts coyote density to be highest along the southwestern edge of the Adirondack State Park, including Tug Hill, and lowest in the mature forests and more rural areas of the central and eastern Adirondacks. Together, these results support the need for a nuanced view of how eastern coyotes use forested habitats.