The interaction between philopatry and nonrandom mating has important consequences for the genetic structure of populations, influencing co-ancestry within social groups but also inbreeding. Here, using genetic paternity data, we describe mating patterns in a wild population of red deer (Cervus elaphus) which are associated with marked consequences for co-ancestry and inbreeding in the population. Around a fifth of females mate with a male with whom they have mated previously, and further, females frequently mate with a male with whom a female relative has also mated (intralineage polygyny). Both of these phenomena occur more than expected under random mating. Using simulations, we demonstrate that temporal and spatial factors, as well as skew in male breeding success, are important in promoting both re-mating behaviours and intralineage polygyny. However, the information modelled was not sufficient to explain the extent to which these behaviours occurred. We show that re-mating and intralineage polygyny are associated with increased pairwise relatedness in the population and a rise in average inbreeding coefficients. In particular, the latter resulted from a correlation between male relatedness and rutting location, with related males being more likely to rut in proximity to one another. These patterns, alongside their consequences for the genetic structure of the population, have rarely been documented in wild polygynous mammals, yet they have important implications for our understanding of genetic structure, inbreeding avoidance and dispersal in such systems.