Studies on social networks illuminate social dynamics within a single species, but seldom consider interactions between species, even when species co-occur and fill similar niches. Our study focused on the social structures of two sympatric species, Long-nosed leopard lizards (G. wislizenii) and Western whiptails (A. tigris), in the Alvord Basin Desert, Oregon. Although they occupy the same habitat and consume the same prey, the species exhibit opposite forms of sexual dimorphism and rely on different foraging methods that allow them to partition niche space. To determine the extent to which interactions between the species signify an interspecific social network, we conducted focal observations and recorded inter- and intraspecific interactions (i.e., aggression, mating, mutual tolerance, avoidance). We characterized social networks by assessing each individual’s centrality (i.e., degree, betweenness) relative to its own and to the other species. We also analyzed patterns of association within and between species relative to sex and snout-vent length and found that interactions varied within and between demographic classes, and that the two species differed in social network structure. In addition, we found intraspecific differences based on sex and body size in degree distributions and patterns of association. Interspecific interactions differed from the expectations of random networks. Our results provide evidence of a complex social structure within and between the species, which merits further study to determine the interplay between social status, interspecific relationships, and behavior.