Habitat selection theory predicts that individuals choose breeding habitats that maximize fitness returns on the basis of indirect environmental cues at multiple spatial scales. We performed a 3-year field experiment to evaluate five alternative hypotheses regarding whether individuals choose breeding territories in heterogeneous landscapes on the basis of (1) shrub cover within a site, (2) forest land-cover pattern surrounding a site, (3) conspecific song cues during prebreeding settlement periods, (4) a combination of these factors, and (5) interactions among these factors. We tested hypotheses with playbacks of conspecific song across a gradient of landscape pattern and shrub density and evaluated changes in territory occupancy patterns in a forest-nesting passerine, the Black-throated Blue Warbler (Dendroica caerulescens). Our results support the hypothesis that vegetation structure plays a primary role during presettlement periods in determining occupancy patterns in this species. Further, both occupancy rates and territory turnover were affected by an interaction between local shrub density and amount of forest in the surrounding landscape, but not by interactions between habitat cues and social cues. Although previous studies of this species in unfragmented landscapes found that social postbreeding song cues played a key role in determining territory settlement, our prebreeding playbacks were not associated with territory occupancy or turnover. Our results suggest that in heterogeneous landscapes during spring settlement, vegetation structure may be a more reliable signal of reproductive performance than the physical location of other individuals.