Brood (social) parasites and their hosts exhibit a wide range of adaptations and counter-adaptations as part of their ongoing coevolutionary arms races. Obligate avian brood parasites are expected to use potential host species with more easily accessible nests, while potential hosts are expected to evade parasitism by building more concealed nests that are difficult for parasites to enter and in which to lay eggs. We used phylogenetically informed comparative analyses, a global database of the world's brood parasites, their host species, and the design of avian host and non-host nests (approx. 6200 bird species) to examine first, whether parasites preferentially target host species that build open nests and, second, whether host species that build enclosed nests are more likely to be targeted by specialist parasites. We found that species building more accessible nests are more likely to serve as hosts, while host species with some of the more inaccessible nests are targeted by more specialist brood parasites. Furthermore, evolutionary-transition analyses demonstrate that host species building enclosed nests frequently evolve to become non-hosts. We conclude that nest architecture and the accessibility of nests for parasitism represent a critical stage of the ongoing coevolutionary arms race between avian brood parasites and their hosts.