The Ghana Empire became Muslim in the 1100's. The subsequent fall of the Ghana Empire and the rise of Islam coincided perfectly. Arab tradition states that the Muslim Almoravids conquered Ghana. While this probably isn't true, there was likely an element of political control involved in maintaining the gold trade. They did invade several times as far as Mali. Moreso, it was the dynastic struggles that the Almoravids encouraged led to the downfall of Ghana, and the rise of Mali. Mali was Muslim and furthered the Islamization of the region.
The Kanem Empire covered a north-south trade route through the middle of the Sahara desert. It began around 700 A.D. and was never invaded by a Muslim power. A dynastic change occured in 1086 and the new king was a convert to Islam. This caused a rift in the society, which would become a recurrent theme in the history of Chad. Today it is 55% Muslim.
The Malacca Sultanate developed on the heels of Singapura. Singapura had become very rich during the Pax Mongolica period, arousing the concern of its neighbors. They overran it and continued to threaten the area. A new port was created up the coast which became a safe haven for merchants, and became the core of the Malacca Sultanate. The leaders were Islamic from an early time.
The sultanate controlled the Malacca straits. When the Champa-Vietnamese war led to the decline of Champa around 1471, Malacca's influence led to the growth of Islam along the Vietnamese coastline. This was the high point of the Sultanate, after which it was invaded by the Portugese.
The Volga Bulgars converted to Islam in 922 A.D. They tried to convert Vladimir I of Kiev without success. Their capitol was Bolghar on the Middle Volga. It was a major center of Eurasian trade in the crusade period. In the later Mongolian period, Bolghar grew exponentially.
The Golden Horde was a Mongolian and Turkic Khaganate in Russia that was independent for most of its existence. Berke Khan, the second Khan who ruled only the western half, converted to Islam around 1240. His conversion was due to his alliance with the Mamluks in Cairo against the Mongolian Ilkhanate in Persia. Widespread Islamization occured in the 14th century, after the conversion of Uzbeg Khan in 1313. The period of Uzbeg was the high point for the Horde. One reason for his conversion to Islam was to remove the influence of eastern Mongolians and Buddhists. The Golden Horde was located in the Transcaucasus, which was an important Trans-Caspian trade route.
As a nuance, the Umayyads had invaded the Transcaucasus 737. They forced the Khazar Khagan to convert to Islam. This was superficial and the Khazars ignored them afterwards.
Islamic merchants had a presence in all of these places since the early Islamic period. The work of the Sufi Orders from about the 10th century made Islam a majority religion in the Middle East, then proceeded to spread it to the extremities of southeast Asia and Africa.
Thanks to Alex for pointing out that the Golden Horde became Muslim.