One predicted cost of female infidelity in socially monogamous species is that cuckolded males should provide less parental care. This relationship is robust across species, but evidence is ambiguous within species. We do not know whether individual males reduce their care when paired with cheating females compared with when paired with faithful females (within-male adjustment) or, alternatively, if the males that pair with cheating females are the same males that provide less parental care in general (between-male effect). Our exceptionally extensive long-term data set of repeated observations of a wild passerine allows us to disentangle paternal care adjustment within males—within pairs and between males—while accounting for environmental variables. We found a within-male adjustment of paternal provisioning, but not incubation effort, relative to the cuckoldry in their nest. This effect was mainly driven by females differing consistently in their fidelity. There was no evidence that this within-male adjustment also took place across broods with the same female, and we found no between-male effect. Interestingly, males that gained more extrapair paternity provided less care. Data from a cross-foster experiment suggested that males did not use kin recognition to assess paternity. Our results provide insight into the role of individual variation in parental care and mating systems.