The discovery and settlement of the tiny and remote Easter Island (Rapa Nui) has been a classical controversy for decades. Present-day aboriginal people and their culture are undoubtedly of Polynesian origin, but it has been debated whether Native Americans discovered the island before the Polynesian settlement. Until recently, the paradigm was that Easter Island was discovered and settled just once by Polynesians in their millennial-scale eastward migration across the Pacific. However, the evidence for cultivation and consumption of an American plant—the sweet potato (Ipomoea batatas)—on the island before the European contact (1722 CE), even prior to the Europe-America contact (1492 CE), revived controversy. This paper reviews the classical archaeological, ethnological and paleoecological literature on the subject and summarizes the information into four main hypotheses to explain the sweet potato enigma: the long-distance dispersal hypothesis, the back-and-forth hypothesis, the Heyerdahl hypothesis, and the newcomers hypothesis. These hypotheses are evaluated in light of the more recent evidence (last decade), including molecular DNA phylogeny and phylogeography of humans and associated plants and animals, physical anthropology (craniometry and dietary analysis), and new paleoecological findings. It is concluded that, with the available evidence, none of the former hypotheses may be rejected and, therefore, all possibilities remain open. For future work, it is recommended to use the multiple working hypotheses framework and the strong inference method of hypothesis testing, rather than the ruling theory approach, very common in Easter Island research.