My name was Abd Amr, and the Messenger of Allah ﷺ named me Abdul-Rahman.
كان اسمي عبد عمرو، فسماني رسول الله ﷺ عبد الرحمن.
Abu Naeem reported it in Marifat al-Sahaba (456), and Hakim graded it sahih (3/306), both through routes from Ibrahim bin Saad bin Ibrahim, who said, "My father narrated to me, from his father, from Abdul-Rahman bin Awf," and he mentioned it. Its chain of transmission is sahih.