Centuries after the Presothians vanished, the region went largely uninhabited and unexplored, with many European and African legends considering the place haunted by the lost peoples, or in Greek legend guarded by the Gods. References to the islands appear largely in Greek and late-period Egyptian mythology, and as the culture of fear of the islands began to dissolve a few adventurers began mapping out and first voyaging into the wilderness of the islands. Around halfway through the era of Greek dominance, North African pagan tribes first began establishing settlements on the southern shores of the archipelago. Towards the end of the Hellenic Period and the dominance of Alexander the Great, Greek merchants arrived on the northern parts of the islands and a few trading colonies were formed, though the interior of the islands went largely unexplored except by a few bold adventurers who were revered as heroic explorers in both Hellenic and North African culture. After the fall of Ancient Greece giving way to the gradual rise of the Roman Empire, many of the Greek trading ports were abandoned. Those that remained first came into close contact with the southern inhabitants around this time and began to intermarry and eventually form the earliest distinct ethnic group which would later become the Arvainians. As the Roman Empire expanded, their legions soon came to the islands and took control. During the first period of Roman dominance on Arvain, the culture started slowly to move away from the African-influenced tribal systems and into a feudal society, though this wouldn't be a permanent evolution.
After a few decades of Roman conquest on Arvain, the islands became known as a region called the Arvesine. The land was rich in resources and the Romans expanded colonies into largely unexplored interior locales of the islands, uncovering many of the lost Presothian tombs. Eventually many of the tribes in Arvain formed a Confederacy and led a successful revolt against Roman Imperial rule and the islands were split into the Arvesine Potentate, a vassal kingdom of the Romans, and the sovereign tribes in the east. The early religious practices of the tribal Arvesine peoples were largely focused on the land and sea, and the region's cultural reverence for nature still influences Arvainian society today. Soon discontent with the Roman Empire's plundering of land and lingering influence, even on the supposedly independent tribal lands of the eastern islands, led to another rebellion. The War of the Red Throne erupted across the islands, the Red Alliance against the Arvesine Potentate and their Roman leaders. The First War of the Red Throne lasted nearly 30 years and resulted in another bitter stalemate, the islands divided between Roman and Tribal rule. Less than ten years later, the Novus Regus was formed, an alliance between the tribes of the former Red Alliance and those inhabiting the Potentate discontent with Imperial rule. The Second War of the Red Throne lasted less than ten years, and resulted in the Roman Empire being finally expelled from the Arvesine. After the expulsion of the Roman Empire, the Novus Regus divided into four tribal kingdoms in a period which is known as the Four Kingdoms Era. This would be the first time ethnic Arvainians, with their own self determination, began to form into a more organized united nation between the four islands of the Arvesine.