In this Letter, we study a localized stellar overdensity in the constellation of Ursa Major, first identified in Sloan Digital Sky Survey (SDSS) data and subsequently followed up with Subaru imaging. Its color-magnitude diagram (CMD) shows a well-defined subgiant branch, main sequence, and turnoff, from which we estimate a distance of ∼30 kpc and a projected size of ∼250 × 125 pc2. The CMD suggests a composite population with some range in metallicity and/or age. Based on its extent and stellar population, we argue that this is a previously unknown satellite galaxy of the Milky Way, hereby named Ursa Major II (UMa II) after its constellation. Using SDSS data, we find an absolute magnitude of Mv ∼ -3.8, which would make it the faintest known satellite galaxy. UMa II's isophotes are irregular and distorted with evidence for multiple concentrations; this suggests that the satellite is in the process of disruption.