Due to their role in mate choice, disease resistance and kin recognition, genes of the major histocompatibility complex (MHC) are good candidates for investigating genetic-based mate choice. MHC-based mate choice is context dependent and influenced by many factors including social structure. Social structure diversity makes the Egernia group of lizards suitable for comparative studies of MHC-based mate choice. We investigated mate choice in the gidgee skink (Egernia stokesii), a lizard that exhibits high levels of social group and spatial stability. Group membership was incorporated into tests of the good genes as heterozygosity and compatible genes hypotheses for adaptive (MHC) and neutral (microsatellite) genetic diversity (n = 47 individuals genotyped). Females were more likely to pair with a male with higher MHC diversity and with whom they had a lower degree of microsatellite relatedness. Males were more likely to pair with a female with higher microsatellite heterozygosity and with whom they shared a lower proportion of MHC alleles. Lizards were more likely to mate with an individual from within, rather than outside, their social group, which confirmed earlier findings for this species and indicated mate choice had already largely occurred prior to either social group formation or acceptance of an individual into an existing group. Thus, a combination of genes and group membership, rather than group membership alone, predicted mate choice in this species. This work will contribute to an enhanced understanding of squamate group formation and a deeper understanding of the evolution of sociality within all vertebrates.