Musnad Abu Ya'la al-Mawsili 250:6

Abu Bakr ibn Abi Shaybah narrated to us, Yahya ibn Ya'la al-Aslami narrated to us, from 'Abd al-Malik ibn 'Umayr, from the nephew of 'Abdullah ibn Salam, from 'Abdullah ibn Salam, who said: My name in the Pre-Islamic period (Jahiliyyah) was so-and-so. The Messenger of Allah (may Allah bless him and grant him peace) named me 'Abdullah.