We combine our Hubble Space Telescope measurement of the proper motion of the Leo I dwarf spheroidal galaxy (presented in a companion paper) with the highest resolution numerical simulations of Galaxy-size dark matter halos in existence to constrain the mass of the Milky Way's dark matter halo (M-vir,M-MW). Despite Leo I's large Galactocentric space velocity (200 km s(-1)) and distance (261 kpc), we show that it is extremely unlikely to be unbound if Galactic satellites are associated with dark matter substructure, as 99.9% of subhalos in the simulations are bound to their host. The observed position and velocity of Leo I strongly disfavor a low-mass Milky Way: if we assume that Leo I is the least bound of the Milky Way's classical satellites, then we find that M-vir,M-MW > 10(12) M-circle dot at 95% confidence for a variety of Bayesian priors on M-vir,M-MW. In lower mass halos, it is vanishingly rare to find subhalos at 261 kpc moving as fast as Leo I. Should an additional classical satellite be found to be less bound than Leo I, this lower limit on M-vir,M-MW would increase by 30%. Imposing a mass-weighted Lambda CDM prior, we find a median Milky Way virial mass of M-vir,M-MW = 1.6 x 10(12) M-circle dot, with a 90% confidence interval of [1.0-2.4] x 10(12) M-circle dot. We also confirm a strong correlation between subhalo infall time and orbital energy in the simulations and show that proper motions can aid significantly in interpreting the infall times and orbital histories of satellites.