We report the discovery by the Swift hard X-ray monitor of the transient source Swift J2058.4+0516 (Sw J2058+05). Our multi-wavelength follow-up campaign uncovered a long-lived (duration > ~ months), luminous X-ray (L sub(X,iso) approximate 3 x 10 super(47) erg s super(-1)) and radio (nuL sub(nu,iso) approximate 10 super(42) erg s super(-1)) counterpart. The associated optical emission, however, from which we measure a redshift of 1.1853, is relatively faint, and this is not due to a large amount of dust extinction in the host galaxy. Based on numerous similarities with the recently discovered GRB 110328A/Swift J164449.3+573451 (Sw J1644+57), we suggest that Sw J2058+05 may be the second member of a new class of relativistic outbursts resulting from the tidal disruption of a star by a supermassive black hole. If so, the relative rarity of these sources (compared with the expected rate of tidal disruptions) implies that either these outflows are extremely narrowly collimated (straighttheta < 1degrees) or only a small fraction of tidal disruptions generate relativistic ejecta. Analogous to the case of long-duration gamma-ray bursts and core-collapse supernovae, we speculate that rapid spin of the black hole may be a necessary condition to generate the relativistic component. Alternatively, if powered by gas accretion (i.e., an active galactic nucleus (AGN)), Sw J2058+05 would seem to represent a new mode of variability in these sources, as the observed properties appear largely inconsistent with known classes of AGNs capable of generating relativistic jets (blazars, narrow-line Seyfert 1 galaxies).