Behavioral differences between individuals that are consistent over time characterize animal personality. The existence of such consistency contrasts to the expectation based on classical behavioral theory that facultative behavior maximizes individual fitness. Here, we study two personality traits (aggression and breath rate during handling) in a wild population of blue tits during 2007-2012. Handling aggression and breath rate were moderately heritable (h (2) = 0.35 and 0.20, respectively) and not genetically correlated (r A = 0.06) in adult blue tits, which permits them to evolve independently. Reciprocal cross-fostering (2007-2010) showed that offspring reared by more aggressive males have a higher probability to recruit. In addition, offspring reared by pairs mated assortatively for handling aggression had a higher recruitment probability, which is the first evidence that both parents' personalities influence their reproductive success in the wild in a manner independent of their genetic effects. Handling aggression was not subjected to survival selection in either sex, but slow-breathing females had a higher annual probability of survival as revealed by capture-mark-recapture analysis. We find no evidence for temporal fluctuations in selection, and thus conclude that directional selection (via different fitness components) acts on these two heritable personality traits. Our findings show that blue tit personality has predictable fitness consequences, but that facultative adjustment of an individual's personality to match the fitness maximum is likely constrained by the genetic architecture of personality. In the face of directional selection, the presence of heritable variation in personality suggests the existence of a trade-off that we have not identified yet.