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