As species move into new environments through founder events, their phenotypes may diverge from native populations. Identifying the drivers underlying such variation and the constraints on the adaptive potential of this variation is essential for understanding how organisms respond to new or rapidly changing habitats. Such phenotypic divergence may be especially evident in populations introduced to new environments via human-assisted transport or in dramatically altered environments such as cities. Sexually dimorphic species beg the additional questions of how these new environments may influence the sexes differently and how dimorphism may shape the range of potential responses. The repeated translocation, establishment, and spread of wall lizards (Podarcis spp.) from native European populations to new locations in North America provide an excellent natural experiment to explore how phenotypes may differ after establishment in a new environment. Here, we quantify body shape and the multivariate morphological phenotype (incorporating limb dimensions and head length) of common wall lizards (P. muralis) and Italian wall lizards (P. siculus) in replicated North American introductions. In both species, males are larger and have larger head length and limb dimensions than females across all sampled groups. Sexual dimorphism in the multivariate morphological phenotype was of similar magnitude when comparing native and introduced populations for both species, though the trajectory angles in multivariate trait space differed in P. siculus. When comparing introduced lizards from contemporary and historically collected museum specimens, we identified differences of similar magnitude but in different trajectories between sexes in P. siculus, and differences in both magnitude and direction of sexual dimorphism in P. muralis. These idiosyncratic patterns in phenotypic trajectories provide insight to the potential array of processes generating phenotypic variation within species at the intersection of invasion biology and urban evolution.