Sedna (provisionally designated 2003 VB12) was discovered by Michael Brown (Caltech), Chad Trujillo (Gemini Observatory), and David Rabinowitz (Yale University) on 14 November 2003. The discovery formed part of a survey begun in 2001 with the Samuel Oschin telescope at Palomar Observatory near San Diego, California using Yale's 160-megapixel Palomar Quest camera. On that day, an object was observed to move by 4.6 arcseconds over 3.1 hours relative to stars, which indicated that its distance was about 100 AU. Follow-up observations were made in November–December 2003 with the SMARTS telescope at Cerro Tololo Inter-American Observatory in Chile, the Tenagra IV telescope in Nogales, Arizona, and the Keck Observatory on Mauna Kea in Hawaii. Combining those with precovery observations taken at the Samuel Oschin telescope in August 2003, and from the Near-Earth Asteroid Tracking consortium in 2001–2002, allowed to accurately determine its orbit. The calculations showed that the object was moving along a distant highly eccentric orbit, at a distance of 90.3 AU from the Sun. Precovery images have later been found in images of the Palomar Digitized Sky Survey dating back to September 25, 1990.
Brown initially nicknamed Sedna "The Flying Dutchman", or "Dutch", after a legendary ghost ship, because its slow movement had initially masked its presence from his team. For an official name for the object, Brown settled on "Sedna," a name from Inuit mythology, which Brown chose partly because the Inuit were the closest polar culture to his home in Pasadena, and partly because the name, unlike Quaoar, would be easily pronounceable. On his website, he wrote, "Our newly discovered object is the coldest, most distant place known in the Solar System, so we feel it is appropriate to name it in honor of Sedna, the Inuit goddess of the sea, who is thought to live at the bottom of the frigid Arctic Ocean." Brown also suggested to the International Astronomical Union's (IAU) Minor Planet Center that any future objects discovered in Sedna's orbital region should also be named after entities in arctic mythologies. The team made the name "Sedna" public before the object had been officially numbered. Brian Marsden, the head of the Minor Planet Center, said that such an action was a violation of protocol, and that some members of the IAU might vote against it. No objection was raised to the name, and no competing names were suggested. The IAU's Committee on Small Body Nomenclature accepted the name in September 2004, and also considered that, in similar cases of extraordinary interest, it might in the future allow names to be announced before they were officially numbered.