While habitat alteration has considerable potential to disrupt important within-population processes, such as mating and kin structure, via changed patterns of dispersal, this has rarely been tested. We are investigating the impact of anthropogenic habitat alteration on the population biology of the rock-dwelling Australian lizard Egernia cunninghami on the Central Tablelands of New South Wales, Australia, by comparing deforested and adjacent naturally vegetated areas. The novel analyses in this paper, and its companion, build on previous work by adding a new replicate site, more loci and more individuals. The additional microsatellite loci yield sufficient power for parentage analysis and the sociobiological inferences that flow from it. Genetic and capture-mark-recapture techniques were used to investigate mate and site fidelity and associated kin structure. Analyses of the mating system and philopatry using 10 microsatellite loci showed high levels of site fidelity by parents and their offspring in natural and deforested habitats. Parentage assignment revealed few individuals with multiple breeding partners within seasons and fidelity of pairs across two or more breeding seasons was typical. Despite reduced dispersal, increased group sizes and significant, dramatic increases in relatedness among individuals within rock outcrops in deforested areas, no significant differences between deforested and natural areas were evident in the degree of multiple mating or philopatry of breeding partners within and across seasons. With the exception that there was a significantly higher proportion of unmated males in the deforested area, the social and mating structure of this species has so far been surprisingly robust to substantial perturbation of dispersal and relatedness structure. Nonetheless, approximately 10-fold elevation of mean pairwise relatedness in the deforested areas has great potential to increase inbred matings, which is investigated in the companion paper.