In the distant future, the known universe is ruled by Padishah Emperor Shaddam IV. The most important substance in the empire is the drug known as melange or "the spice". It has many special properties, such as extending life and expanding consciousness. The most profitable and important of its properties is its ability to assist the Spacing Guild with folding space, which allows safe, instantaneous interstellar travel.
Sensing a potential threat to spice production, the Spacing Guild sends an emissary to demand an explanation from the Emperor, who confidentially shares his plans to destroy House Atreides. The popularity of Duke Leto Atreides has grown though the empire, and he is suspected to be amassing a secret army equipped with sonic-based weapons, which Emperor Shaddam sees a potential threat to his rule. Shaddam's plan is to give House Atreides control of the planet Arrakis (also known as Dune), the only source of spice. Once installed on Arrakis, he intends to have them ambushed by their longtime archenemies, the Harkonnens, with assistance from the Emperor's elite troops, the Sardaukar. The Guild Navigator also commands the Emperor to kill Duke Leto's son, Paul Atreides, a young man who dreams prophetic visions of his purpose. The execution order draws the attention of the Bene Gesserit sisterhood, as Paul is tied its centuries-long Bene Gesserit breeding program which seeks to produce the universe's superbeing, the Kwisatz Haderach. Before he leaves for Arrakis, Paul is tested by the Bene Gesserit Reverend Mother Gaius Helen Mohiam by being forced to place his hand in a box which induces excruciating pain. To her suprise, he passes the test to Mohiam's satisfaction.
Meanwhile, on the industrial world of Giedi Prime, the sadistic Baron Vladimir Harkonnen tells his nephews Glossu Rabban and Feyd-Rautha about his plan to eliminate the Atreides by manipulating someone in House Atreides into betraying the Duke. The Atreides leave their homeworld Caladan for Arrakis, a barren desert planet populated by gigantic sandworms. The native people of Arrakis are called the Fremen, a mysterious people that have long held a prophecy that a messiah would come to lead them to freedom. Upon arrival on Arrakis, Leto is informed by one of his right-hand men, Duncan Idaho, that the Fremen have been underestimated, as they exist in vast numbers and could prove to be powerful allies. Leto begins to gain the trust of the Fremen, but before the Duke can establish an alliance, the Harkonnens launch their attack.
While they had anticipated a trap, Harkonnen's traitor within House Atreides, Dr. Wellington Yueh, Duke Leto's personal physician, has disabled critical shields and has destroyed their sonic weapons, leaving them nearly defenseless. In the attack, Idaho is killed, Leto is captured, and nearly all of House Atreides is wiped out. While captured, Leto dies in a failed attempt to assassinate the Baron Harkonnen using a poison gas capsule planted in his tooth by Dr. Yueh, who is double-crossed by Baron Harkonnnen and executed by Rabban. However, Leto's concubine Lady Jessica and his son Paul survive the attack and are able to escape into the deep desert, where they discover a siectch of Fremen, led by Stilgar. Paul and Jessica are taken in by the Fremen; Jessica becomes their Reverend Mother, and Paul falls in love with Chani, a Fremen warrior he'd previously seen in one of his visions.
Paul takes on the Fremen name Muad'Dib, and emerges as the leader for whom the Fremen have been waiting. He teaches the Fremen to build and use the sonic weapons developed by House Atreides and begins to target spice mining production, which is back in control of the Harkonnen, overseen by Rabban. Over the next two years, spice production is effectively halted, a fact Rabban tries to keep hidden from the empire. The Spacing Guild return to the Emperor to warn him of the deteriorating situation on Arrakis. They also fear that Paul will consume the Water of Life, a powerful poison used by the Bene Gessseit to help induce their abilities. The meeting is revealed to Paul in a prophetic dream, but then, the dreams suddenly stop. Shaken by the absence of his visions, he goes out into the desert and drinks the Water of Life and enters into a trance. Upon awakening, he is transformed, obtaining powerful psychic abilities and the ability to control the sandworms. Paul has also regained his ability to see into space and the future, and learns the Emperor is amassing a huge invasion fleet above Arrakis to wipe out the Fremen and to regain absolute control of the planet.
Upon the Emperor's arrival at Arrakis, he executes Rabban for failing to remedy the spice situation, calling in Baron Harkonnen to demand an explanation. At the same time, Paul launches a final attack against the Harkonnens and the Emperor's Sardaukar at the capital city of Arrakeen. His Fremen warriors, riding in on sandworms and brandishing their sonic weapons, easily defeat the Emperor's legions, while Paul's sister Alia kills Baron Harkonnen. Once in Arrakeen, Paul faces the Emperor and engages Feyd-Rautha in a duel to the death; Paul kills Feyd and relieves Emperor Shaddam of power. Paul then demonstrates his newfound powers and fulfills the Fremen prophecy that he is the promised messiah by causing rain to fall on Arrakis for the first time ever, as Alia declares him to be the Kwisatz Haderach.

Question: Who has long held the belief that a messiah was coming to lead them to safety?
Answer: The Fremen, the native people of Arrakis