We have imaged the extended HI environment of M31 with an unprecedented combination of high resolution and sensitivity. We detect a number of distinct High Velocity Cloud components associated with M31. A sub-set of the features within 30 kpc appear to be tidal in origin. A filamentary ``halo component is concentrated at the M31 systemic velocity and appears to extend into a ``bridge connecting M31 and M33. This may represent condensation in coronal gas. A population of discrete clouds is detected out to radii of about 150 kpc. Discrete cloud line-widths are correlated with HI mass and are consistent with a 100:1 ratio of dark to HI mass. These may be the gaseous counterparts of low-mass dark-matter satellites. The combined distribution of M31s HVC components can be characterized by a spatial Gaussian of 55 kpc dispersion and yields an N_HI distribution function which agrees well with that of low red-shift QSOs.