أهل المدينة عنده؛ فأجمع أهل المدينة على عبد الملك بن يحيى وسألوه أن يخرج؛ فخرج في ذلك ورفع حوائجهم، وأقام بالعراق يطالبها، وكان رجلا موسرا وباع من أبي عبيد الله عينا له - يقال لها: ملح بساية - بعشرة آلاف دينار، ثم جاءه كتاب أنه ولد له غلام ولم يكن له ابن قبل ذلك؛ فاستقال أبا عبيد الله فأقاله، وانصرف إلى المدينة.
وقال محمد بن عبد الملك الأسدي [من البسيط]:
امدح كريم بني العوام إن له مناقبا لم ينلها قبله بشر حاشى النبي وقوم قد مضوا معه هم الذين إليه دارهم هجروا أعني ابن يحيى بن عباد فإن له سوابق المجد قد قرت بها مضر عبد المليك الذي عمت صنائعه كما يعم البلاد المحلة المطر قد أحكمته النهى في حسن تجربة فهو البصير بما يأتي وما يذر إني وجدت بني يحيى إذا جهروا هم البحور بحور المجد والغرر قال: وقال أيضا يمدحه [من البسيط]:
إن الكرام جروا حتى إذا اختلفوا وجاش كل كريم الجري سباق وأبصر الناس من يفري ذوي مهل صاف وعز وأحلام وأعراق