We present a suite of semi-analytic disk-bulge-halo models for the Andromeda galaxy (M31) which satisfy three fundamental conditions: (1) internal self-consistency; (2) consistency with observational data; and (3) stability of the disk against the formation of a central bar. The models are chosen from a set first constructed by Kuijken and Dubinski. We develop an algorithm to search the parameter space for this set in order to best match observations of the M31 rotation curve, inner velocity dispersion profile, and surface brightness profile. Models are obtained for a large range of bulge and disk masses; we find that the disk mass must be of order 8 * 10^10 M_sun and that the preferred value for the bulge mass is 2.5 * 10^10 M_sun. N-body simulations are carried out to test the stability of our models against the formation of a bar within the disk. We also calculate the baryon fraction and halo concentration parameter for a subset of our models and show that the results are consistent with the predictions from cosmological theories of structure formation. In addition, we describe how gravitational microlensing surveys and dynamical studies of globular clusters and satellites can further constrain the models.