Background: Polyandry is a common mating strategy in animals, increasing female fitness through direct (material) and indirect (genetic) benefits. Most theories about the benefits of polyandry come from studies of terrestrial animals, which have relatively complex mating systems and behaviors; less is known about the potential benefits of polyandry in sessile marine animals, for which potential mates may be scarce and females have less control over pre-copulatory mate choice. Here, we used microsatellite markers to examine multiple paternity in natural aggregations of the Pacific gooseneck barnacle Pollicipes elegans, testing the effect of density on paternity and mate relatedness on male reproductive success. Results: We found that multiple paternity was very common (79% of broods), with up to five fathers contributing to a brood, though power was relatively low to detect more than four fathers. Density had a significant and positive linear effect on the number of fathers siring a brood, though this relationship leveled off at high numbers of fathers, which may reflect a lack of power and/or an upper limit to polyandry in this species. Significant skew in male reproductive contribution in multiply-sired broods was observed and we found a positive and significant relationship between the proportion of offspring sired and the genetic similarity between mates, suggesting that genetic compatibility may influence reproductive success in this species. Conclusions: To our knowledge, this is the first study to show high levels of multiple paternity in a barnacle, and overall, patterns of paternity in P. elegans appear to be driven primarily by mate availability. Evidence of paternity bias for males with higher relatedness suggests some form of post-copulatory sexual selection is taking place, but more work is needed to determine whether it operates during or post-fertilization. Overall, our results suggest that while polyandry in P. elegans is driven by mate availability, it may also provide a mechanism for females to ensure fertilization by compatible gametes and increase reproductive success in this sessile species.