Reproductive success of brood parasites largely depends on appropriate host selection and, although the use of inadvertent social information emitted by hosts may be of selective advantage for cuckoos, this possibility has rarely been experimentally tested. Here, we manipulated nest size and clutch colouration of magpies (Pica pica), the main host of great spotted cuckoos (Clamator glandarius). These phenotypic traits may potentially reveal information about magpie territory and/or parental quality and could hence influence the cuckoo's choice of host nests. Experimentally reduced magpie nests suffered higher predation rate, and prevalence of cuckoo parasitism was higher in magpie nests with the densest roofs, which suggests a direct advantage for great spotted cuckoos choosing this type of magpie nest. Colouration of magpie clutches was manipulated by adding one artificial egg (blue or cream colouration) at the beginning of the egg-laying period. We found that host nests holding an experimental cream egg experienced a higher prevalence of cuckoo parasitism than those holding a blue-coloured egg. Results from these two experiments suggest that great spotted cuckoos cue on magpie nest characteristics and the appearance of eggs to decide parasitism, and confirm, for the first time, the ability of cuckoos to distinguish between eggs of different colours within the nest of their hosts. Several hypothetical scenarios explaining these results are discussed.