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