Musannaf Ibn Abi Shayba 3:5482

'Abbad ibn al-'Awwam narrated to us, from Husayn al-Maktab, from 'Amr ibn Shu'ayb, from his father, from his grandfather: That the Prophet, may Allah bless him and grant him peace, used to pray barefoot and wearing sandals.