The mosque was first erected in the 14th century by the Moors.^{[citation needed]} It is assumed that they constructed the mosque so that their merchants could pray while trading on this part of the Adriatic Coast. The fact that the mosque was erected before Islam was established in Ulcinj indicates the surprise of the Ottomans, having found the sacred place at the sea shore in 1571.

Ibrahim Pasha of Scutari (1797-1809) had the mosque rebuilt in appreciation for having survived the Battle of Krusi. He dedicated the mosque to the Ulcinj sailors who contributed to his family's success, hence the name – Sailors' Mosque. The small cultural center was established in 1798 and also served as a religious school and shelter for travelers and the poor.

The mosque was closed and removed in 1931.

In 1880, Ulcinj was occupied by Great Power forces and was given to the Principality of Montenegro. After World War I Montenegro became part of the Kingdom of Serbs, Croats and Slovenes. In 1931 the military demolished the mosque. After 81 years it was rebuilt by private investors from Alanya, Turkey with the help of the Islamic Union of Montenegro and the Municipality of Ulcinj.

As a part of Montenegro, under the control of Ottoman Empire, Ulcinj assimilated in both religion and tradition. Local custom dictated that after major events or battles, the residents of the town should erect a mosque as a symbol of their gratitude to God. Additionally, mosques represented the backbone of a town, influencing its architecture and spiritual life.

The private houses in the mosque's vicinity were designated for congregants. Therefore, leisure time and family life became more fully integrated with daily prayers.

On 4 November 2013, lightning partially damaged the top of the minaret.

• Ulcinj
• List of mosques in Ulcinj
• List of the oldest mosques