In 863, he made his way from Samarra to Bahrain (modern eastern Arabia), where he pretended to be Shi'i and started to rouse the people into rebellion against the caliphate. Support for his cause quickly grew. A large number of Bahranis submitted to his authority and the "kharaj" (land taxes) were collected in his name. Despite this, his rebellion eventually failed due to opposition from the local inhabitants, whereupon 'Ali abandoned the region and relocated to the city of Basra in southern Iraq in 868. In Basra 'Ali sought to take advantage of disturbances caused by the city's rival groups, the Bilaliyyah and Sa'diyyah, and attempted to secure the support of one of the factions. Eventually he proclaimed a new revolt, but no one in the city rallied to his side and he was forced to flee to the marshlands of southern Iraq. There he was arrested by the provincial authorities and sent to Wasit. He was quickly able to secure his freedom and went to Baghdad, where he remained for the next year. During his time in Baghdad he claimed to be a Zaydi by being related to the grandson of Zayd ibn Ali and won over additional followers for his movement. When 'Ali heard news about another scuffle between Basra's factions in 869, he returned to the region and "began to seek out black slaves working in the Basra marshes and to inquire into their working conditions and nutritional standards." He began a campaign to liberate and recruit Zanj and other slaves, promising them freedom and wealth in exchange for their support. A large number of people quickly joined his cause, and 'Ali soon came to be known by the title "Sāhib az-Zanj", meaning "Chief of the Zanj". However, 'Ali's movement attracted not only Zanj but many other socially downtrodden peoples. These included "semi-liberated slaves, clients of prestigious families, a number of small craftsmen and humble workers, some peasantry and some Bedouin peoples who lived around Basrah." While he was gaining followers for his rebellion, 'Ali adopted slogans of the egalitarian doctrine of the Kharijites, who "preached that the most qualified man should reign, even if he was an Abyssinian slave." He inscribed his banner and coins with Kharijite expressions and started off his Friday sermons with the slogan "God is great, God is great, there is no God but God, and God is great; there is no arbitration except by God," which was "the war cry used by the Kharijites when they defected from the ranks of Ali ibn Abi Talib during the battle of Siffin."