Background: In cooperative breeders, subordinates generally help a dominant breeding pair to raise offspring. Parentage studies have shown that in several species subordinates can participate in reproduction. This suggests an important role of direct fitness benefits for cooperation, particularly where groups contain unrelated subordinates. In this situation parentage should influence levels of cooperation. Here we combine parentage analyses and detailed behavioural observations in the field to study whether in the highly social cichlid Neolamprologus pulcher subordinates participate in reproduction and if so, whether and how this affects their cooperative care, controlling for the effect of kinship. Methodology/Principal Findings: We show that: (i) male subordinates gained paternity in 27.8% of all clutches and (ii) if they participated in reproduction, they sired on average 11.8% of young. Subordinate males sharing in reproduction showed more defence against experimentally presented egg predators compared to subordinates not participating in reproduction, and they tended to stay closer to the breeding shelter. No effects of relatedness between subordinates and dominants (to mid-parent, dominant female or dominant male) were detected on parentage and on helping behaviour. Conclusions/Significance: This is the first evidence in a cooperatively breeding fish species that the helping effort of male subordinates may depend on obtained paternity, which stresses the need to consider direct fitness benefits in evolutionary studies of helping behaviour.