Tereny wokół miasta były już zamieszkane w epoce brązu. Pierwszymi właścicielami tych ziem byli Ilirowie. Ulcinj został założony w V w. p.n.e. Wtedy też przybyli tutaj greccy kolonizatorzy z okolic Kolchidy (starożytna kolonia grecka na wybrzeżu Morza Czarnego – obecnie terytorium Gruzji). Utworzoną osadę nazwano Kolchinium. Co ciekawe nazwa miejscowości figuruje już w dokumentach, które datuje się na III w. p.n.e. (o tych terenach wspomina grecki poeta Apollonios z Rodos). W 163 r. p.n.e. okolicę podbijają Rzymiane. Miasto zmienia swoją nazwę na Olcinium. Po upadku Cesarstwa Rzymskiego Ulcinj stał się częścią Bizancjum. Od tego czasu aż do średniowiecza miejscowość była nazywana „gniazdem piratów” oraz „stolicą handlu niewolnikami”. W 1183 roku miasto zostaje podbite przez Symeona Serbskiego (założyciela dynastii Nemaniczów). Miejscowość się rozwija i staje się jednym z największych miast na wybrzeżu Morza Adriatyckiego. W 1356 roku serbski król Stefan Urosz V Nijaki przekazał Ulcinj wraz z okolicą swojemu wasalowi Balsze I (założycielowi dynastii Balšiciów). Za czasów panowania tej dynastii w mieście została wybudowana mennica. W 1423 roku Ulcinj zostaje podbity przez Republikę Wenecką. Wenecjanie zmieniają nazwę miasta na Dulcigno. Miejscowość staje się częścią Albanii Weneckiej. W czasie trwania wojny z Imperium Osmańskim to właśnie w Ulcinje ukrywało się większość chrześcijan. W mieście nadal zajmowano się handlem czarnymi niewolnikami. Ich potomkowie żyją tutaj do dzisiaj. W 1571 roku miejscowość została zdobyta przez Imperium Osmańskie. Z tym wydarzeniem związana jest ciekawa historia. Jak głosi legenda, hiszpański pisarz Miguel de Cervantes y Saavedra dostał się właśnie tutaj do tureckiej niewoli. Mówi się, że Dulcynea z Toboso (fikcyjna postać w powieści „Don Kichot”), tak naprawdę to jedna z ówczesnych mieszkanek Ulcinja. W latach 1672–1676 w tutejszej twierdzy był więziony Szabetaj Cewi (rabin i twórca ruchu sabataistycznego-heretyckiego, judaistycznego ugrupowania religijnego). Rabin przyjął jednak islam i zmarł w Ulcinje. Natomiast w 1878 roku w wyniku ustaleń kongresu berlińskiego tereny te zostały włączone do księstwa Czarnogóry. Po I wojnie światowej miasto weszło w skład Królestwa Serbów, Chorwatów i Słoweńców. W czasie trwania drugiej wojny światowej stacjonowały tu wojska niemieckie i włoskie. W 1944 roku Ulcinj został wyzwolony spod faszystowskiej dominacji. Po zakończeniu światowego konfliktu miasto zostało odbudowane.

Stare Miasto (Stari Grad) – jest jednym z wielu na czarnogórskim wybrzeżu Morza Adriatyckiego. Otacza go wysoki, kamienny mur, bronią go fortece. Zabudowania Starego Miasta liczą 3 ha. Mury obronne natomiast sąsiadują bezpośrednio z morzem. Kompleks składa się z cytadeli (która niegdyś pełniła funkcję obronną i militarną). Za budowniczych Starego Miasta uważa się Greków z Epiru. Pierwsze zabudowania wznieśli oni w V w. p.n.e. To, co jednak wznieśli greccy murarze, zostało zniszczone przez trzęsienie ziemi. W późniejszym czasie to właśnie Rzymianie projektują nowy układ urbanistyczny.

Stare Miasto to historyczne dziedzictwo Ulcinja. Tuż obok bramy północnej znajduje się muzeum, w którym można zapoznać się z ciekawą historią tego regionu. Najcenniejszy eksponat to kamea z wizerunkiem greckiej bogini Artemidy. Z kolei kamienna wieża Balsici jest przykładem średniowiecznej architektury. Tuż przed budynkiem znajduje się Plac Niewolników. Jak sama nazwa wskazuje, niegdyś przetrzymywano tutaj czarnoskórych niewolników. Ciekawym obiektem jest także wieża Balani, która powstała za panowania Republiki Weneckiej. Znajduje się tu też turecka fontanna z pitną wodą z 1749 roku. Ciekawe zbiory posiada Muzeum Etnograficzne.

Ada Bojana – kompleks położony na południe od Ulcinja. Znajduje się na rzece Buna, która wpada do Morza Adriatyckiego. Sztuczna wyspa powstała w XIX wieku, kiedy na mieliźnie osiadł statek. Rzeka przez lata nanosiła tutaj osady rzeczne. Znajduje się tu specjalnie wyznaczona strefa dla nudystów. Teren otoczony jest przez rzekę i słoną, morską wodę. Przebywający tu turyści w strojach Adama i Ewy zwykli mawiać, że jest to raj na ziemi i najlepsze miejsce na szalone wakacje. Znajduje się tu długa, piaszczysta plaża. Nad Buną natomiast położone są luksusowe bungalowy, które można wynająć. Tylko 100 metrów dzieli letniskowe domki od kompleksu dla nudystów. W tutejszych restauracjach można skosztować dań z owoców morza.

Wielka Plaża (Velika plaža) – znajduje się 2 km od miasta. Długa na 13 km z szarym piaskiem, który podobno ma właściwości lecznicze. Jest to jedna z najdłuższych plaż na wybrzeżu Morza Adriatyckiego.