Збудована на фундаменті католицької церкви Святого Стефана Першомученика[1].

Напис на арабському фундаменті мечеті говорить, що побудований на замовлення Мехмеда Бека б. Абу аль-Саадат, який був братом візира в році хіджри 965 (1557-58). Деякі вчені стверджують, що візиром був великий візир Рустем-паша, але у Рустем-паші записаний лише один брат Сінан-паша[2].

Мечеть, можливо, була спроектована імператорським архітектором Мімаром Сінаном. Вона має форму купоподібного куба, обрамленого подвійним портиком. Три куполи внутрішнього портика підтримуються чотирма мармуровими колонами. Зовнішній портик має підвісний дах, що спирається на невеликі восьмикутні колони. Великий купол мечеті висотою 10,65 м розташований на восьмикутному барабані з отворами, що підтримується восьмикінцевими арками[2].

Мечеть серйозно пошкоджена під час Другої світової війни та майже повністю зруйнована під час Боснійської війни на початку 1990-х. Як і решта Мостара, зазнала масштабного ремонту в 2002-2004. Повністю відремонтована та знову відкрита для публіки у липні 2004.