Avian obligate brood parasites, which rely solely on hosts to raise their young, should choose the highest quality hosts to maximize reproductive output. Brown-headed cowbirds (Molothrus ater) are extreme host generalists, yet female cowbirds could use information based on past reproductive outcomes to make egg-laying decisions thus minimizing fitness costs associated with parasitizing low quality hosts. We use a long-term (21 years) nest box study of a single host, the prothonotary warbler (Protonotaria citrea), to show that local cowbird reproductive success, but not host reproductive success, was positively correlated with the probability of parasitism the following year. Experimental manipulations of cowbird success corroborated that female cowbirds make future decisions about which hosts to use based on information pertaining to past cowbird success, both within and between years. The within-year pattern, in particular, points to local cowbird females selecting hosts based on past reproductive outcomes. This, coupled with high site fidelity of female cowbirds between years, points to information use, rather than cowbird natal returns alone, increasing parasitism rates on highly productive sites between years.