We present new mass estimates for Andromeda (M31) using the orbital angular momenta of four satellite galaxies (M33, NGC 185, NGC 147, IC 10) derived from existing proper motions, distances, and line-of-sight velocities. We infer two masses for M31: Mvir=2.85+1.47−0.77×1012M⊙ using satellite galaxy phase space information derived with HST-based M31 proper motions and Mvir=3.02+1.30−0.69×1012M⊙ using phase space information derived with the weighted average of HST+Gaia-based M31 proper motions. The precision of our new M31 mass estimates (23-50%) improves by a factor of two compared to previous mass estimates using a similar methodology with just one satellite galaxy and places our results amongst the highest precision M31 estimates in recent literature. Furthermore, our results are consistent with recently revised estimates for the total mass of the Local Group (LG), with the stellar mass--halo mass relation, and with observed kinematic data for both M31 and its entire population of satellites. An M31 mass >2.5×1012M⊙ could have major implications for our understanding of LG dynamics, M31's merger and accretion history, and our understanding of LG galaxies in a cosmological context.