To examine how territorial males counter reproductive parasites, we examined the paternity of broods guarded by territorial males using 5 microsatellite loci and factors that determine siring success in a wild population of the Lake Tanganyika cichlid Lamprologus lemairii. Females enter rock holes (nests) and spawn inside, and territorial males release milt over the nest openings. Sneakers attempt to dart into the nests, but territorial males often interrupt the attempt. The body size of territorial males (territorial defense ability) and the size of nest opening (the ability to prevent sneakers from nest intrusions) are predicted to be factors that affect paternity at the premating stage, whereas milt quality traits are factors that affect paternity at the postmating stage. Parentage analyses of 477 offspring revealed that most clutches have few or no cuckolders, and territorial males sired >80% of eggs in 7 of the 10 analyzed clutches. Larger territorial males that spawned in nests with narrower openings had greater siring success. In contrast, none of the milt traits affected the siring success. These suggest that territorial male L. lemairii adopt premating strategies whereby they effectively prevent reproductive parasitism.