According to some historical accounts such as those recorded in the Shah-Nama, the Zensunni ancestors of the Fremen arrived on Arrakis from many different planets. The Wandering Zensunni, also known as the Zensunni Wanderers, traveled from one world to another in search of freedom from persecution and enslavement by the Imperial raiders.
Beginning of the Migration
By 2800 AG, the Guild rediscovered hundreds of habitable unpopulated worlds. Under the Right of Domain rulings in the Great Convention the House paying the Guildsmen for a planetary find gained dominion over that planet, conditional upon the approval of the Landsraad Council and the Emperor, something that no House could expect to meet the Imperial revenues demanded, without being able to establish a workforce there.
Since the House often could not populate the planet, most Houses were content to relinquish all claim to a find and offer it, instead, as an Imperial Colony. If accepted, such an offer netted the House a handsome finder's fee, and left the problem of populating the new colony with the Throne. The emperor, being eminently practical in such matters, would spread the costs in lost manpower with "volunteer" settlers.
Having accepted Poritrin from House Maros, Emperor Elrood V turned a covetous eye on the population of Terra and demanded a levy of two million people from Siridar Baron Charles Mikarrol of Old Terra. The Baron was thrown into a quandary because Terrans, so accustomed to their exemption from Imperial draft, were certain to rebel at the news.
One of his advisers (perhaps Ari Manoud, his right-hand man and an outspoken Maometh Saari) — reminded him of the existence of the Zensunni nomads. By the end of their planet-wide search and seizure, the troops had uncovered more ton 2.5 million Zensunni, and were herded aboard Imperial transports over their most outraged protests, and whisked off to Poritrin.
Migration of the Wandering Zensunni
Though much of the history of the Wandering Zensunni was lost to the Fremen, some information was kept alive through oral tradition. However, even prior to the emergence of the prescient Paul Atreides, many non-Fremen expressed doubts over the validity of the stories, thanks to linguistic and mythological traditions.
Poritrin
Poritrin, the third planet of Epsilon Alangue is remembered as their planet of origin in the Fremen memories.
On their arrival they acted not like terrified exiles, but like a people accustomed to challenges. Tribes, each obedient to the commands of its naib worked in concert to divide the machinery and other resources the transport ships had left, decide on the areas to be settled and disperse.
Daiwid Kuuan records in his Monuments of the Zensunni Migrations a song fragment thought to be from this period:
...and though our enemies scatter us far, even throughout the Universe, they shall never destroy us. For we are Misr, the People, and to us have been revealed the Fiqh and Ilm [the half-legendary sources of the Zensunni faith] which none other have seen. This remains. We remain.
Poritrin had a plentiful supply of water, a long growing season, and a gentle climate combined to make the work of settling the planet unusually light, leisure time was frequently spent in reshaping and adapting the mystic doctrines and superstitions of the sect, and much of the reshaping concerned itself with the Zensunni's lost point of origin.
By 3500 AG, many of the Ulema and Sayyadina preached that the Zensunni had fled Nilotic al-Ourouba ("The Place of Truth and Mystery") to escape persecution and death. Nilotic al-Ourouba was believed to be the place in which the ten thousand sunnah would be answered, but this would not take place until the Zensunni's time on Poritrin was completed. Then, they would make a great hajra to Nilotic al-Ourouba to seek those answers.
By the end of 4000 AG most Zensunni were taught and believed that Poritrin was their original homeworld. Only a small, select number of the Sayyadina passed on the truth concerning the migration from one generation to the next.
The easy living affected their societal makeup drastically. A large number of people could be comfortably fed and housed on a relatively small land area and had a stable population in permanent settlements, some of them comparable in size to small cities of the Imperium reaching a population of 10 million. The nomadic lifestyle, the fierce insistence on independence—were abandoned.
However the Landsraad wished the planet and the new Zensunni were no match for the raiders who came in 4492 AG. The existing population divided between colonies on Bela Tegeuse and Salusa Secundus.
They had simply accepted the arrival of the force as a fulfilling of the prophecies concerning the hajra until a handful of the craftiest Sayyadina managed to learn the actual destinations of the heighliners. When they were found, was torture and death at the hands of their captors. The Zensunni on both ships were wailing: "They denied us the Hajra!"
Salusa Secundus
Half (5 million), the relatively pampered, were sent to Salusa Secundus, third planet of Gamma Waiping with an ecological system so harsh that 6/13 died before the age of eleven. The death rate was higher to non natives and the Zensunni stuck to their sense of loyalty and communit.
There, the troops and Sardaukar tried to break their spirit, used them as slaves and had them perform the most difficult and dangerous tasks. As they resisted, they were subjected to more rigorous oppression each generation.
During the first generation, thousands and hundreds of thousands died within the first few years, but most of them reverted to the difficult way of living in the Sahara.
Eventually at the end of this generation, the off-planet Zensunni were exhibiting a survival rate which compared very favorably to that of those born on Salusa Secundus.
The third generation was subjected to ever more rigorous oppression, and proved more resilient than the second.
The fifth generation was commanded to give up the faith or die; all known Sayyadina, and over half the population were butchered but the doctrines continued to be passed on in the slaves' disguised work chants. New Sayyadina were initiated as quickly as the old could be spied out.
In the seventh and eighth generations the Sardaukar tried to convert them to their mystic disciplines. Each time, the Zensunni either completely ignored the attempt, or feigned going along with the conversion until the weapons training. At that point, the "convert" killed as many of his fellow students and instructors as possible before killing himself.
In the ninth generation, in 5295 AG, Ezhar VII reviewed the records of his ancestors' failures with the Zensunni and announced that it was not his policy "to punish people whose only crime lay in having had criminal forebears", and arranged for them to be transferred to Ishia.
Bela Tegeuse
The other half were sent to relative security on Bela Tegeuse, fifth planet of Kuentsing.
All inhabited Ishia within fifty generations of their arrival at Arrakis.
Rossak
On Rossak their Reverend Mothers became acquainted with the poison drug that let their direct chain of "ancestral" memory supplement the Wanderers' oral legends.
Evidence from the Imperial Records about Rossak implies that the Bene Gesserit's Missionaria Protectiva/DE and Panoplia Propheticus/DE apparatus was grafted to them.
Harmonthep and Ishia
The majority of those taken from Bela Tegeuse in 6049 AG dwelt for a time on [Harmonthep/DE|Harmonthep]], before ending up on Arrakis. Of this stay nothing is known other than the world had a random magnetic field, and so they invented the paracompass.
The refugees from Rossak were given a comprehensive explanation about their people who had been out of reach for so long. The Guildsmen spoke as little as possible of on Salusa Secundus.
Ishia was the opposite of Rossak: hot, arid, oppressing to its life forms with heat as Rossak did with cold. Crops which survived did so only because of tremendous amounts of time and energy spent in careful irrigation. The system had to be constantly watched, as a single day's deprivation could kill a field.
The Zensunni had come from a tougher environment but adapting was difficult. Not accustomed to the workings of a desert ecology. Eventually they had done well by reverting to many of the ways of their ancestors from the time of the nomadic tribes, by living with the desert instead of struggling against it
In Kuuan's Monuments it is recorded that Ishia was the training ground for Arrakis, where all the Zensunni finally went.
Arrakis
In 7193 AG, all known Zensunni in the Imperium were transported to Arrakis. This last relocation of the hajra, organized in deep secret by the Spacing Guild, served the purposes of both sides involved since it gave them a home on a world where they would be too difficult to dig out. They also gave the Guild a permanent entree to Arrakis and its spice.
The ensured that the Zensunni were established deep enough inside the desert far from those settlers already on Arrakis (concentrated chiefly in Arrakeen, the seat of government), then withdrew.
From that point on, the Zensunni recognized themselves not as a religion but as a people, and they called themselves "Fremen".