In many species of birds, the quality of the nest site may have important fitness consequences. The focus of the present study was to see if nest box choice in blue tits (Cyanistes caeruleus) and great tits (Parus major) is mainly genetically determined or if it is based on early learning, and also if one sex is more involved in the selection than the other. If it is based on early learning, the birds may learn when they are in their natal nest and/or by observing the behavior of conspecifics after fledging. The study area was a natural habitat containing nest boxes of two sizes, where the general observation is that blue tits prefer small and great tits large nest boxes. The methods adopted were a comparison between size of nesting box and natal box, observation of the same individual’s choice in successive years, and a study of the effect of interspecific cross-fostering. Cross-fostering resulted in more blue tits being reared in large nest boxes, and more great tits in small nest boxes, than in the case of controls, and gave an opportunity for cross-fostered individuals to learn from a different foster species. None of the results seemed to indicate a strong effect of either inheritance, based on genetic variation at the individual level, or cultural transmission. Blue tits seemed to prefer small nest boxes regardless of the size of their natal box or the species of the rearing parents. The exception was cross-fostered blue tit females in heterospecific pairs (male great tit x female blue tit) that had been reared in a large nest box. These females tended to nest in large nest boxes. In great tits, most controls preferred large nest boxes, while cross-fostered individuals, especially the females, tended to use small nest boxes. Alternative explanations, based on competition for nest sites and female condition (laying date of first egg, clutch size and egg volume) were also considered. However, with a possible exception of clutch size in great tits, none seemed to explain the patterns observed. Choice of nest site in blue tits and great tits may primarily be a general trait at the species level, where blue tits prefer small nest boxes and great tits prefer large. It may thus have a genetic basis, but with little variation among individuals within the species.Males and females were analyzed separately in the main analyses, and the results suggest that, at least in great tits, the female is the most influential in nest site choice, but that the male may have some influence. This is reasonable, because the female builds the nest and incubates the clutch, whereas both parents feed the young.