Tatkala tampuk khilafah beralih ke tangan Abdul Malik bin Marwan, Amirul Mukminin menulis surat kepada gubernurnya di Irak, Hajjaj bin Yusuf; “Hendaknya engkau mengirim kepadaku seorang yang mahir dalam hal agama dan dunia, yang akan aku jadikan sebagai teman dan pendampingku”.
Lalu diutuslah Asy Sya’bi dan Amirul Mu’minin berkenan menjadikannya sebagai pendamping dan memanfaatkan ilmunya ketika menghadap kesulitan, memakai pandangannya setiap kali membutuhkan dan menjadikan dia sebagai utusannya untuk bernegosiasi dengan raja-raja di muka bumi.
Suatu kali Asy Sya’bi diutus untuk urusan penting menemui Justinian kaisar Romawi. Setibanya beliau di Romawi dan setelah memberikan keterangan, Kaisar Romawi kagum akan kecerdasan dan kelihaiannya, serta takjub akan keluasan wawasan dan kekuatan daya tangkapnya.
Dia bahkan meminta kesediaan Asy Sya’bi untuk memperpanjang kunjungannya sampai beberapa hari, sesuatu yang tidak pernah dilakukan Kaisar terhadap para utusan yang lain.
Ketika Asy Sya’bi mendesak agar segera diizinkan pulang ke Damaskus, Justinian bertanya; “Apakah Anda dari keturunan raja-raja?”. Ia menjawab; “Tidak, saya seperti umumnya kaum muslimin”.
