تعود تسمية المسجد إلى سليمان باشا الخادم الذي عُين واليا على مصر من قبل السلطان العثماني سليمان القانوني لفترتين؛ الأولى من سنة 931هـ إلى سنة 941هـ (1525- 1535م) والثانية من سنة 943هـ إلى سنة 945هـ (1536- 1536م)، وقد قام أثناء ولايته على مصر ببعض أعمال التشييد والبناء؛ منها هذا المسجد الذي أقامه عام 935هـ/1528م بالقاهرة.

وكان المسجد في البداية؛ مسجدا فاطميا يعرف بمسجد (قسطة)؛ نسبة لأبي منصور قسطة والي الإسكندرية خلال العصر الفاطمي، وهو غلام أرمني من غلمان المظفر ابن أمير الجيوش وقد مات مسموما من أكلة هريسة كما ذكر المقريزي، وكان من عقلاء الأمراء، وقام بإنشاء مسجده عام 535هـ/1141م.

أما المسجد الحالي، فقد أقامه سليمان باشا بقلعة الجبل (قلعة صلاح الدين) بالقسم الشمالي الشرقي منها، وكان قد خصصه للجنود الإنكشارية، حيث بناه تحقيقاً لرغبة الجنود؛ الذين كان ولاةُ مصر من الباشوات يبذلون كل جهدهم كي يظل هؤلاء الجند مقيمين بمساكنهم بسور الإنكشارية أو سور صلاح الدين، وحتى يظلوا أيضا بمعزل عن جند الغرب الذين كانوا يقيمون بالجانب الآخر من القلعة من باب السلسلة تجاه جامع السلطان حسن، وكان من دواعي بنائه أيضا أن جامع الناصر محمد بن قلاوون قد أهمل أمره وندر التردد عليه، وكان من الضروري إقامة بناء مسجد جديد.

وقد ذُكر مسجد سليمان باشا في الخطط التوفيقية، بأنه: "في قلعة الجبل مشهور، وبقربه زاوية الشيخ محمد الكعكعي، وبه منبر خشب ودكة، وله منارة ومطهرة وأخلية، وله أوقاف دارّة، وشعائره الإسلامية مقامة،... وينسب الجامع إلى سيدي سارية رضي الله عنه صاحب رسول الله صلى الله عليه وسلم؛ كما هو شائع على الألسنة"، هكذا قال عنه علي مبارك.

أما المقريزي فقد أشار إلى ذلك الاسم أيضا وقال؛ إن قلعة الجبل كانت مقبرة بنيت فيها عدة مساجد ومنها مسجد قسطة، وقد ذكر ابن جبير مشهد سارية الجبل كذلك، ولكن علق على ذلك بأنه لم يُذكر في كتب التاريخ أن سارية الجبل قدم إلى مصر ضمن الصحابة الذين جاءوها.

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

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

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