We report the discovery and early observations of the peculiar Type IIn supernova (SN) 2006gy in NGC 1260. With a peak visual magnitude of about -22, it is the most luminous supernova ever recorded. Its very slow rise to maximum took åisebox-0.5ex 70 days, and it stayed brighter than -21 mag for about 100 days. It is not yet clear what powers the enormous luminosity and the total radiated energy of i̊sebox-0.5ex 10$^51$ erg, but we argue that any known mechanism-thermal emission, circumstellar interaction, or $^56$Ni decay-requires a very massive progenitor star. The circumstellar interaction hypothesis would require truly exceptional conditions around the star, which, in the decades before its death, must have experienced a luminous blue variable (LBV) eruption like the 19th century eruption of η Carinae. However, this scenario fails to explain the weak and unabsorbed soft X-rays detected by Chandra. Radioactive decay of $^56$Ni may be a less objectionable hypothesis, but it would imply a large Ni mass of rs̊ebox-0.5ex 22 M$_solar$, requiring SN 2006gy to have been a pair-instability supernova where the star's core was obliterated. While this is still uncertain, SN 2006gy is the first supernova for which we have good reason to suspect a pair-instability explosion. Based on a number of lines of evidence, we eliminate the hypothesis that SN 2006gy was a ``Type IIa’’ event, that is, a white dwarf exploding inside a hydrogen envelope. Instead, we propose that the progenitor was a very massive evolved object like η Carinae that, contrary to expectations, failed to shed its hydrogen envelope. SN 2006gy implies that some of the most massive stars can explode prematurely during the LBV phase, never becoming Wolf-Rayet stars. SN 2006gy also suggests that they can create brilliant supernovae instead of experiencing ignominious deaths through direct collapse to a black hole. If such a fate is common among the most massive stars, then observable supernovae from Population III stars in the early universe will be more numerous than previously believed.