Studies of habitat selection are often of limited utility because they focus on small geographic areas, fail to examine behavior at multiple scales, or lack an assessment of the fitness consequences of habitat decisions. These limitations can hamper the identification of successful site-specific management strategies, which are urgently needed for severely declining species like Cerulean Warblers (Setophaga cerulea). We assessed how breeding habitat decisions made by Cerulean Warblers at multiple scales, and the subsequent effects of these decisions on nest survival, varied across the Appalachian Mountains. Selection for structural habitat features varied substantially among areas, particularly at the territory scale. Males within the least-forested landscapes selected microhabitat features that reflected more closed-canopy forest conditions, whereas males in highly forested landscapes favored features associated with canopy disturbance. Selection of nest-patch and nest-site attributes by females was more consistent across areas, with females selecting for increased tree size and understory cover and decreased basal area and midstory cover. Floristic preferences were similar across study areas: White Oak (Quercus alba), Cucumber-tree (Magnolia acuminata), and Sugar Maple (Acer saccharum) were preferred as nest trees, whereas red oak species (subgenus Erythrobalanus) and Red Maple (A. rubrum) were avoided. The habitat features that were related to nest survival also varied among study areas, and preferred features were negatively associated with nest survival at one area. Thus, our results indicate that large-scale spatial heterogeneity may influence local habitat-selection behavior and that it may be necessary to articulate site-specific management strategies for Cerulean Warblers.