We present an analysis of the positions and velocities of M31 globular clusters, which indicates the presence of significant substructure in the globular cluster system. We suggest this clustering is the surviving signature of gaseous clumps out of which the halo of M31 formed. A mixture-modeling analysis of the metallicity distribution of the M31 globulars indicates that, like the Milky Way, the metallicity distribution is bimodal. We show that the metallicity of genuine halo clusters in the Milky Way and M31 is similar to that of globulars around nearby dwarf galaxies. This suggests that such clusters formed from primordial material, whereas the disk globulars in the Galaxy and M31, as well as metal-rich globulars in elliptical galaxies, formed in some secondary event