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