In conjunction with the wider Fremen legend of salvation, the Mahdi was also known to be an off-worlder (i.e. not a native of Arrakis), and the child of a Bene Gesserit. Thus, after Paul Atreides fell in with the Fremen and first displayed his prescience and fighting skills, many Fremen gradually began to see the young Duke as the Mahdi.
The legend associated with the Mahdi was at least partially influenced by a long-standing Panoplia Propheticus by the Bene Gesserit's Missionaria Protectiva wing. Lady Jessica noted that the Mahdi legend's presence on Arrakis was an indication of just how awful conditions there were, since it was reserved only for those cultures where a Bene Gesserit would need to assume total control.