Na njega se prvo doselilo ratoborno pleme Paštrovići. Napravili su luksuzne kuće, grad opasali kao tvrđavu, podigli tri crkve.
Ostrvo je nazvano prema istoimenoj crkvi posvećenoj arhiđakonu Stefanu Prvomučeniku.
Crkva je bila sagrađena još u vrijeme Nemanjića na najuzvišenijem dijelu ostrva.
Paštrovići su sa Nemanjićima bili u dobrim odnosima. Osim crkve Sveti Stefan, na ostrvu se nalaze i crkva Aleksandra Nevskog i crkva na samom ulazu u gradić, posvećena Preobraženju.
Tvrđava je na ostrvu sagrađena 1442. godine kada je i naseljena prvim stanovnicima. Zidine su štitile stanovništvo od gusara i Turaka, a legenda kaže da je do izgradnje došlo upravo zbog turske opsade grada Kotora, nakon čega su Paštrovići i Kotorani zajednički branili grad, izvojevajući na kraju pobjedu.
Od stečenog plijena su podigli tvrđavu koja je dugo bila središte paštrovskog suda, pa se ovo mjesto naziva još i mjestom od pravde.
Ovaj sud je bio veliki ponos Paštrovića, a vodio je porijeklo još iz 1266. godine kada ga je odobrio kralj Stefan Prvovjenčani.
Najstariji pisani izvor u kome se pominje paštrovski sud je 1431. godine, kada su Paštrovići dobrovoljno ušli u sastav Mletačke republike zbog opasnosti od Turaka.
Sveti Stefan je posjedovao i veliki strateški i trgovinski značaj u vrijeme Mletačke republike i trgovine s Venecijom.
Međutim, u 19. vijeku mahom ribarsko stanovništvo počinje da se iseljava.
Kraljevska porodica Karađorđevića vodi spor sa vlastima Crne Gore i traži da im se vrati kompletan posjed Svetog Stefana, koji su tvrde u devetnaestom vijeku za velike pare kupili od Paštrovića.
Komunistička vlast pod vodstvom Josipa Broza Tita, preotela je svojinu nad ostrvom 1945. godine i od njega napravilo luksuzan turistički kompleks.
Grad hotel posjećivali su brojni slavni gosti poput La Pasionarije, maršala Timošenka, pisaca Anri Malroa i Moravije, kompozitora Mikisa Teodorakisa, glumačke zvijezde Sofija Loren, Monika Viti, Kirk Daglas, Silvester Stalone.
Godine 1992. na njemu je odigran meč Fišer Spaski.
Posljednjih godina zbog različitih sudskih sporova i neriješenog vlasništva Grad hotel ne radi.
Postojala je priča da je Novak Đoković bio zaineteresovan da kupi Sveti Stefan, ali je izgleda odustao.
Vjerovatno su brojni potomci Paštrovića zainteresovani za kupovinu. Ili da im se posjed restitucijom vrati.
Bilo bi veoma zanimljivo znati šta se tačno trenutno dešava sa možda najvećim biserom Jadrana.
