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 sub-giant branch, main sequence and turn-off, from which we estimate a distance of ~30 kpc and a projected size of ~250 x 125 pc. 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 M_V ~ -3.8, which would make it the faintest known satellite galaxy. UMa IIs isophotes are irregular and distorted with evidence for multiple concentrations; this suggests that the satellite is in the process of disruption.