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

فلما سمع أبو عبيدة كلام البطرك تبسم وقال: فتحنا البلد ورب لكعبة، ثم أقبل على البطرك وقال: إن رأيت الرجل تعرفه، قال: نعم، وكيف لا أعرفه؟ قال أبو عبيدة: هو والله خليفتنا وصاحب نبينا، قال البطرك: فإذا كان الأمر على ما ذكرت فاحقن الدماء وابعث إلى صاحبك فإذا رأيناه وتبيّنا نعته فتحنا له البلد وأعطيناه الجزية، فلما بعث أبو عبيدة في طلبه وأقدم عليهم عمر بمرقعته ونظر إليه البطرك زعق وقال: هذا والله الذي صفته في كتبنا وخرج ومن معه يسألونه العهد.