Recently, The President of India, Dr. A P J Abdul Kalam visited the Cheraman Juma Musjid in Kodungallur (ancient Muziris) in Kerala. This mosque, believed to have been built by Malik bin Dinar in 629 AD, is considered to be the oldest mosque in India. If this date is accurate, then this mosque was established much before the time of Adi Shankara (if we go by the dates ascribed by the Sringeri Peetam) and around the same time Huen Tsang was in India. This mosque has quite a history
As the tradition goes, a Chera king, Cheramanperumal of Kodungallure, left for Makkah, embraced Islam, and accepted the name Thajudeen. He married the sister of then King of Jeddah. On his return trip, accompanied by many Islamic religious leaders, led by Malik-ibn-Dinar (RA), he fell sick and passed away. But he had given introductory letters for the team to proceed to ‘Musiris’ (Kodungallur, the Chera capital. The visitors came to Musiris and handed over the latter to the reigning king, who treated the guests with all respect and extended facilities to establish their faith in the land. The king also organised help for the artisans to build the first Mosque at Kodungallur, by converting Arathali temple into a Juma-Masjid. It was build in 629 A.C., and the area around it had been ear-marked for the team’s settlement.[Cheraman Juma Masjid A Secular Heritage]
This story seems to be a myth propagated in the book Keralolpathi (The origin of Kerala) and repeated many times over. None of the reputed history books mention this story, even the ones by eminent historians. According to Sreedhara Menon
The Cheraman legend is not corroborated by any contemporary record or evidence. None of the early or medieval travelers who visited Kerala has referred to it in their records. Thus Sulaiman, Al Biruni, Benjamin of Tuleda, Al Kazwini, Marco Polo, Friar Odoric, Friar Jordanus, Ibn Babuta, Abdur Razzak, Nicolo-Conti – none of these travelers speaks of the story of the Cheraman’s alleged conversion to Islam.
A mention of the Cheraman Perumal legend appeared in the 16th century book Tuhafat-ul Mujahidin by Shaik Zainuddin, but he too did not believe in its historical authenticity. But later cut and paste historians seem to have forgot to add his disclaimer.
Sreedhara Menon also authoritatively states that Kerala never had a king called Cheraman Perumal and quotes Dr. Herman Gundert, the German who composed the first Malayalam-English dictionary and the grandfather of Herman Hesse for this. But there seems to have been a Cheraman Perumal, whose history is overlaid by legend. According to Saiva tradition, he had an association with a Sundaramurti, the last of the three hymnists of Devaram. This Cheraman Perumal vanished in 825 A.D, about 200 years after Muhammed thus confirming that all that Mecca trip was a fanciful legend.
Update (Jan 1, 2009): Maddy has detailed post about this episode
 Picture of the old mosque and the renovated one
 India Archaeology Messages 2112, 2123