Abstract Deep interferometric observations of CO and dust continuum emission are obtained with the Submillimeter Array at 230 GHz to investigate the physical nature of the giant molecular cloud (GMC) population in the Andromeda galaxy (M31). We use J = 2 − 1 12CO and 13CO emission to derive the masses, sizes, and velocity dispersions of 162 spatially resolved GMCs. We perform a detailed study of a subset of 117 GMCs that exhibit simple, single-component line profile shapes. Examining the Larson scaling relations for these GMCs, we find (1) a highly correlated mass–size relation in both 12CO and 13CO emission; (2) a weakly correlated 12CO line width–size (LWS) relation along with a weaker, almost nonexistent, 13CO LWS relation, suggesting a possible dependence of the LWS relation on spatial scale; and (3) that only 43% of these GMCs are gravitationally bound. We identify two classes of GMCs based on the strength and extent of their 13CO emission. Examination of the Larson relations finds that both classes are individually characterized by strong 12CO mass–size relations and much weaker 12CO and 13CO LWS relations. The majority (73%) of strong 13CO-emitting GMCs are found to be gravitationally bound. However, only 25% of the weak 13CO-emitting GMCs are bound. The resulting breakdown in the Larson relations in the weak 13CO-emitting population decouples the mass–size and LWS relations, demonstrating that independent physical causes are required to understand the origin of each. Finally, in nearly every aspect, the physical properties of the M31 GMCs are found to be very similar to those of local Milky Way clouds.