Sayyiduna Abu Malik al-Ashja'i (may Allah be pleased with him) narrates from his father: When a man accepted Islam, the Prophet (peace and blessings be upon him) would first of all teach us the prayer. The narrator is unsure; perhaps the words are: he would teach him the prayer.
Al-Bazzar, and al-Tabarani in al-Mu'jam al-Kabir, recorded it, and its narrators are the narrators of the Sahih.
Hadith Referenceمجمع الزوائد ومنبع الفوائد / كتاب الصلاة / 1618