Osnivanje Ulcinja vezuje se za nastanak države ilirskog plemena Ardijeja u V. vijeku prije nove ere. Mnoštvo predmeta materijalne kulture koje je ovdje pronađeno prilikom iskopavanja svjedoči o osnivanju Ulcinja prije 2,5 milenijuma, prije svega zid i bedem na sjevernoj strani Starog grada. Taj bedem podignut je u dobro poznatoj grčkoj tehnici zidanja velikim kvaderima, grubo otesanim, pravilno položenim i čisto (tj. suvo) spojenim.
Tu svakako spadaju i fragmenti antičkih crnofiguralnih vaza i bijelih lekita (vrsta grčke keramičke posude za držanje ulja kojim se prije kupanja mazalo tijelo) s crvenom bojom. Do samog ilirsko-grčkog bedema nađena je, takođe iz V. stoljeća, antička gema (minijaturno obrađeni kamen s reljefnim prikazom ljudske figure, samo lika ili neke scene).
Međutim, najznačajniji je, bez sumnje, pronalazak dosada jedinog grčkog natpisa na antičkom postolju za žrtvenik od istog žutog, ali zrelog kamena kojim su zidani bedemi Ulcinium-a, pa se zaključuje da su njegovi graditelji Grci, a za račun Ilira. Kult Artemide – boginje lova – najprije je njegovan u Arkadiji, a zatim, zajedno sa kultom njenog brata Apolona, na ostrvu Delu i u Delfima.
U pisanim izvorima ima veoma malo istorijskih podataka o antičkom Olciniumu; pominju ga poznati rimski istoričari Tit Livije i Plinije Stariji. Tit Livije, govoreći o posljednjem ilirskom ratu vođenom protiv Rima (168. pne), pominje njegove stanovnike. A Plinije Stariji (14-79) u svojoj knjizi Naturalis Historiae Ulcinj navodi kao utvrđeni grad rimskih građana (oppidum civium Romanorum) ističući da se prvobitno zvao Colchinium jer su ga, navodno, osnovali Kolhiđani, iz čega se izvodio zaključak da je bio kolhiđanska kolonija, odnosno da je bio poznat i legendarnim Argonautima.
Gruzinski naučnici dozvoljavaju etimološku mogućnost postanka naziva Olchinium od Colchinium i dalje od Colchis (grčki), pa Qilha – Qulha (urartski). Čuveni njemački ilirolog A. Majer smatra da je naziv Ulcinium izveden od indoevropske osnove ulkas – vuk, imena totemske životinje grada. I hrvatski jezikoslovac Petar Skok povezuje ime Ulcinja (Ulcinium, L’cinj, Ocinj, Ulcinj, Ulqin) sa albanskom riječi ujk (ilirski ulk) – vuk.
Zahvaljujući položaju koji mu je pružao mogućnost da kontroliše široku pučinu mora, Olcinium je u ilirskoj državi imao važnu ulogu, a ovuda su prolazili i značajni putevi.
Protiv ilirske države Rimljani su vodili tri velika rata s namjerom da suzbiju njen uticaj na moru.
U posljednjem ilirsko-rimskom ratu uhvaćen je zadnji veliki ilirski vladar Gencije (168), a gradovi i plemena pod njegovom vlašću izgubili su samostalnost. Tit Livije bilježi da su se stanovnici Olciniuma – Olciniatas – zajedno sa Isejcima, Taulantima, Pirustima i Rizonitima predali Rimljanima bez borbe zbog čega su dobili imunitet koji ih je, između ostalog, oslobađao plaćanja ratne štete.
O životu Ulcinjana u to vrijeme svjedoče arheološki nalazi; pored mnogih fragmenata keramike i drugih predmeta materijalne kulture, otkriven je i dio jednog bedema naslonjen na ilirsko-grčki. Bio je građen velikim kvaderima.
Pod Rimljanima Olcinium je dobio status grada (oppidum civium Romanorum), a to znači da je bio naseljen italskim doseljenicima koji su imali sva rimska građanska prava, dok su ih Iliri stekli kasnije, pošto su već bili jednim dijelom romanizovani.
Kada je riječ o duhovnom životu u starom vijeku u Ulcinju dolazi do izražaja snaga domorodačkog elementa. Tu su posebno zastupljeni ilirski bog vode i mora Bindi (Bindus), te kult zmije, svete životinje Ilira, i ilirski konjanik bog-Medaur, uz još neka druga ilirska božanstva.
