ولما بلغ عمر بن عبد العزيز الخامسة والعشرين، اختاره الخليفة الأموي الوليد بن عبد الملك ليكون واليًا على المدينة وحاكمًا لها، ثم ولاه الحجاز كله، فنشر الأمن والعدل بين الناس، وراح يعمِّر المساجد، بادئًا بالمسجد النبوي الشريف، فحفر الآبار، وشق الترع، فكانت ولايته على مدن الحجاز كلها خيرًا وبركة، شعر فيها الناس بالأمن والطمأنينة.
واتخذ عمر بن عبد العزيز مجلس شورى من عشرة من كبار فقهاء المدينة على رأسهم التابعي الجليل (سعيد بن المسيِّب) فلم يقطع أمرًا بدونهم، بل كان دائمًا يطلب منهم النصح والمشورة، وذات مرة جمعهم، وقال لهم:
إني دعوتكم لأمر تؤجرون فيه، ونكون فيه أعوانًا على الحق، ما أريد أن أقطع أمرًا إلا برأيكم أو برأي من حضر منكم، فإن رأيتم أحدًا يتعدَّى أو بلغكم عن عامل (حاكم) ظلامة فأُحرج بالله على من بلغه ذلك إلا أبلغني، فشكروه ثم انصرفوا، وظل عمر بن عبد العزيز في ولاية المدينة ست سنوات إلى أن عزله الخليفة الوليد بن عبد الملك لأن الحجاج أفهمه أن عمر أصبح يشكل خطرًا على سلطان بني أمية.
ذهب عمر إلى الشام ومكث بها إلى أن مات الوليد بن عبد الملك، وتولى الخلافة بدلاً منه أخوه سليمان بن عبد الملك، وكان يحب عمر، ويعتبره أخًا وصديقًا ويأخذ بنصائحه، وذات يوم مرض الخليفة مرض الموت، وشعر بأن نهايته قد اقتربت، فشغله أمر الخلافة حيث إن أولاده كلهم صغار لا يصلحون لتولي أمور الخلافة، فشاور وزيره (رجاء بن حيوة) العالم الفقيه في هذا الأمر، فقال له:
إن مما يحفظك في قبرك ويشفع لك في أخراك، أن تستخلف على المسلمين رجلا صالحًا.
قال سليمان: ومن عساه يكون؟
قال رجاء: عمر بن عبد العزيز.
فقال سليمان: رضيت، والله لأعقدن لهم عقدًا، لا يكون للشيطان فيه نصيب، ثم كتب العهد، وكلف (رجاء) بتنفيذه دون أن يَعْلَمَ أحدٌ بما فيه.