We report on results of an all-sky search for high-energy neutrino events interacting within the IceCube neutrino detector conducted between May 2010 and May 2012. The search follows up on the previous detection of two PeV neutrino events, with improved sensitivity and extended energy coverage down to about 30 TeV. Twenty-six additional events were observed, substantially more than expected from atmospheric backgrounds. Combined, both searches reject a purely atmospheric origin for the 28 events at the 4σ level. These 28 events, which include the highest energy neutrinos ever observed, have flavors, directions, and energies inconsistent with those expected from the atmospheric muon and neutrino backgrounds. These properties are, however, consistent with generic predictions for an additional component of extraterrestrial origin.