I heard the Messenger of Allah ﷺ say, as he left the mosque heading toward Safa, "We begin with what Allah began with."
أخبرنا محمد بن سلمة قال أنبأنا عبد الرحمن بن القاسم قال حدثني مالك عن جعفر بن محمد عن أبيه
سمعت رسول الله ﷺ حين خرج من المسجد وهو يريد الصفا وهو يقول نبدأ بما بدأ الله به
[Its chain of transmission is sahih] Ahmad narrated it: 3/388, from the hadith of Malik through this route, and it is in Muwatta: 1/372, and in Kubra, no. 3963.