We investigated factors underlying variation in male mating success in Uganda kob (Kobus kob thomasi), a lek-breeding antelope. We found that only heavy (and, possibly, relatively old) males held lek territories and that female choice was an important determinant of nonrandom mating patterns at leks. Our measure of male mating success was closely related to the historical popularity of the territory that a male defended, and individual females showed consistent preferences for particular lek territories, despite changes in territory ownership. Male success increased with body weight and declined independently of territory effects during each bout of lek territory tenure. We also found some evidence that female kob copied one another's choice of mates because females arriving at a lek tended to join territories that already had relatively large harems on them. When compared across leks, average male mating success increased with lek size. Our results suggest that female kob may use a suite of male- and territory-based cues in mate choice at leks and, as a result, mate with particularly large males. However, we were unable to determine whether female kob gain any direct or indirect benefits through mate choice at leks.