In lek-based mating systems only a few males are expected to obtain the majority of matings in a single breeding season and multiple mating is believed to be rare. We used 13 microsatellites to genotype greater sage-grouse (Centrocercus urophasianus) samples from 604 adults and 1206 offspring from 191 clutches (1999–2006) from Alberta, Canada, to determine paternity and polygamy (males and females mating with multiple individuals). We found that most clutches had a single father and mother, but there was evidence of multiple paternity and intraspecific nest parasitism. Annually, most males fathered only one brood, very few males fathered multiple broods, and the proportion of all sampled males in the population fathering offspring averaged 45.9%, suggesting that more males breed in Alberta than previously reported for the species. Twenty-six eggs (2.2%) could be traced to intraspecific nest parasitism and 15 of 191 clutches (7.9%) had multiple fathers. These new insights have important implications on what we know about sexual selection and the mating structure of lekking species.