An important factor in the dynamic transmission of HIV is the mobility of the population. We formulate various stochastic models for the spread of HIV in a heterosexual mobile population, under the assumptions of constant and varying population sizes. We also derive deterministic and diffusion analogues for these models, using a convenient rescaling technique, and analyze their stability conditions and equilibrium behavior. We illustrate the dynamic behavior of the models and their approximations via a range of numerical experiments.