Studies of birds have recently played an important role in the increasing success of quantitative genetics applied to natural populations. However, these studies mostly base their pedigree relationships on social information, despite the known widespread genetic polygamy in avian species. Here, we study the influence of misassigned paternities, combined with the effect of pedigree size and depth, on the estimation of heritability. First, we compute simulations of a polygenic trait for two levels of heritability (0.1 and 0.4), several extra-pair paternity rates (ranging from 5% to 40%), and varying sample sizes (20, 50 and 100 broods) or pedigree depth (2 or 4 generations). We compare heritability estimates from the social and the genetic pedigree, running a restricted maximum-likelihood 'animal model'. Social pedigree underestimates heritability by an average of 0-17% for 5-20% extra-pair paternities and by up to 18% for 40% extra-pair paternities and a heritability of 0.4. Second, we identifyied extra-pair offspring using microsatellite loci in two populations of blue tits (Parus caeruleus) showing high levels of extra-pair paternities (15% and 25% of extra-pair offspring). We compare heritabilities of tarsus length and body mass estimated with pedigrees of increasing accuracy. These analyses suggest that the bias induced by misassigned paternities on heritability estimation depends on the level of heritability and the rate of paternity error. Typical rates of extra-pair paternities in birds (around 20% of offspring) should result in an underestimation of heritability of less than 15% when estimated over a minimum of 100 broods.