Virtual reality (VR) allows users to walk to explore the virtual environment (VE), but this capability is constrained by real obstacles. Teleporting interfaces overcome this constraint by allowing users to select a position, and sometimes orientation, in the VE before being instantly transported without self-motion cues. This study investigated whether individual differences in navigation performance when teleporting correspond to characteristics of the individual, including spatial ability. Participants performed triangle completion (traverse two outbound path legs, then point to the path origin) within VEs differing in visual landmarks. Locomotion was accomplished using three interfaces: walking, partially concordant teleporting (teleport to change position, rotate the body to change orientation), and discordant teleporting (teleport to change position and orientation). A latent profile analysis identified three classes of individuals: those who performed well overall and improved with landmarks (“Accurate Integrators”), those who performed poorly without landmarks but improved when available (“Inaccurate Integrators”), and those who performed poorly even with landmarks (“Inaccurate Non-Integrators”). Characteristics of individuals differed across classes, including gender, self-reported spatial ability, mental rotation, and perspective-taking; but only perspective-taking significantly distinguished all three classes. This work elucidates spatial cognitive correlates of navigation and provides a framework for identifying susceptibility to disorientation in VR.