The passport is issued by the Ministry of Internal Affairs or, if the citizen resides abroad, by a Montenegrin embassy or consulate.

During the reign of Prince-Bishop Petar I Petrović-Njegoš, a special document known as "passport" (Serbian: Пасош) was granted to the citizens who wanted extraordinarily to visit foreign countries.

[3] It was composed of the seal of the Cetinje Metropolitanate's righteous soviet, a bicephalic white eagle with spread-out wings, an Eastern Orthodox cross between his heads, and a passing lion beneath it, altogether on a red background.

With the secularization of Montenegro as a formal princedom under Prince Danilo I Petrovic-Njegos, religious affiliation and even physical description of the passport holder were introduced as of the mid 19th century, in attempt to prevent fraud.

[4] The seal was replaced with Danil's coat of arms, the lion was moved onto a red shield on the eagle's chest, and an imperial crown was added.

Following the breakup of Yugoslavia, passports were issued in order with the Law on Travel Documents of Yugoslav Nationals, which came into force on 26 July 1996, although the country came into existence in 1992.

They were navy blue in color and have two inscriptions in golden letters – Савезна Република Југославија (Federal Republic of Yugoslavia) at the top and the word "passport" written in three languages: Serbian (Cyrillic script), English, and French at the bottom divided by the coat of arms.