Mahmudiye Camii, Sultan 2. Mahmud döneminde 1823’te, dönemin Köstence askerî kumandanı Hafız Hüseyin Paşa tarafından kendi masrafıyla yaptırılmış ve Sultan 2. Mahmud’a ithaf edilmiştir. 1910’da yeni caminin temeline yerleştirilen tarihî belgede yapım yılı 1823 olarak kaydedilmekle birlikte, bazı kaynaklarda 1822 tarihi de verilmektedir. Mahmudiye Camii de aynı yerde bulunan, 18. yüzyıldan kalma daha eski ve küçük bir taş caminin yerine yapılmıştır.
Köstence’nin gelişmesiyle eski yapı kaldırılarak 1910’da yıkılmış, aynı yerde 1910–1913 yıllarında bugünkü Köstence Ulu Camii (Kral Camii / Carol I Camii) inşa edilmiştir. Mahmudiye Camii’nin Mağribî üsluptaki mihrabı kesin olarak korunarak yeni camiye aktarılmıştır; Păuleanu ve Coman’ın araştırmasına dayanan kaynaklara göre minberi de Mahmudiye Camii’nden alınmıştır.
