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 630 kpc and a projected size of 6250 x 125 pc super(2). 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 Mv6-3.8, which would make it the faintest known satellite galaxy. UMall's isophotes are irregular and distorted with evidence for multiple concentrations; this suggests that the satellite is in the process of disruption.