Najstariji tragovi života na otoku sežu u mlađi paleolitik, dok se kroz period neolitika već razvijaju organizirane zajednice o čemu nam svjedoče nalazi keramike. U brončano doba dolaze u ove krajeve ilirska plemena, od kojih su otok Pag kao i susjedna područja nastavali Liburni. Oni osnivaju gradinska naselja na brežuljcima koji su na širem prostoru Novalje i danas vidljivi. O željeznom dobu (9 – 5 st. pr. Kr.) svjedoče tragovi metalnog nakita pronađenog u grobovima uokolo gradina.

Prodor rimskih osvajača kroz 1. st. pr. Kr. nije zaobišao otok na kojem pokoravaju Liburne i trajno učvršćuju svoju vlast. Rimska kultura time je utisnula svoj trag za više stoljeća, a njeni refleksi obilježili su prvo tisućljeće. Naselje Cissa na prostoru Novalje postaje središte otoka, a njenu ubikaciju trebamo tražiti na prostoru Novalja – Caska – Košljun. Iz prvog stoljeća sačuvan je jedinstveni rimski akvedukt zvan Talijanova buža izduben u živom kamenu u dužini preko kilometra i povezivao je Novaljsko polje s lukom na prostoru Novalje. Brojni tragovi života sačuvani iz tog vremena svjedoče o intenzivnom životu prvih stoljeća po Kristu. Kroz 4. i 5. stoljeće u Novalji postoji jaka kršćanska zajednica, podižu se tri velebne bazilike što upućuje da je ranokršćanska Novalja bila i poznato hodočasničko središte antičkog svijeta. Takvo stanje zadržalo se do seobe naroda, kada Novalja kao i cijeli otok u rušilačkim napadima strepi za opstanak.

Brojni arheološki nalazi ovog razdoblja sačuvani su na raznim lokalitetima. Treba istaknuti monumentalni relikvijar pohranjen pored "bazilike urbane", zatim brojni ulomci crkvenog namještaja koji se danas čuvaju u arheološkoj zbirci “Stomorica”. Hrvati dolaze na otok Pag početkom 7. st., a kroz 8. i 9. st. formiraju svoju državu koja se vezuje uz Papu. U vrijeme narodnih vladara Cissa se razvija u značajno gradsko središte za čije posjede i utjecaj se bore okolne komune i plemićke obitelji. Kroz 11. i 12. st. dolazi do podjele otoka Paga između rapske i zadarske komune, i tada oni učvršćuju svoju vlast svatko na svom dijelu otoka. Novalja i zapadni dio otoka pripadaju rapskoj komuni i biskupiji što im je dao hrvatski kralj Petar Krešimir IV. Hrvatsko-ugarski vladari i Mletačka Republika vodili su žestoku borbu za dalmatinske gradove i otoke od 12.–14. st. Na otoku se nastavljaju sukobi Raba i Zadra za prevlast. Utvrđeni grad Kissa, Zadrani su 1203. do temelja razorili poslije čega se ona nije uspjela oporaviti. Početkom 15. st. većina dalmatinskih gradova i otoka dolazi trajno pod mletačku vlast koja će trajati gotovo 4 stoljeća. Interesi gradova bili su podređeni Mletačkoj Republici, koja je kontrolirala sudsku i vojnu vlast. U tom vremenu spominje se Novalja kao manje naselje gdje je rapska komuna imala svog podkneza koji je upravljao njenim posjedima. Za to vrijeme grade se manje zavjetne crkvice na širem prostoru Novalje kao što su Sv. Vid na Vidasovim stanima, Sv. Mihovil na Šankovim stanima, Sv. Ivan na Šonjovim stanima, Sv. Marija na Metajni, Sv. Marija na Staroj Novalji i dr.

Potkraj 18. st. Napoleon ukida Mletačku Republiku i otok Pag dolazi pod upravu Austrije od 1797. – 1805. Nakon poraza Austrije u sukobu s Francuskom otok Pag kao i čitava Dalmacija dolaze pod desetogodišnju francusku vlast. Na Bečkom kongresu 1815. Austrija dobiva ponovno vlast koja je organizirana kao “Kraljevina Dalmacija” sve do 1918. pod upravom Beča i namjesnika u Zadru. Promjena vlasti nije se posebno odrazila na stanovništvo sve do 1848. kad se javlja narodni preporod čiji je cilj ujedinjenje Dalmacije s Hrvatskom i uvođenje hrvatskog jezika u škole i upravu. Nacionalna svijest teži većoj političkoj samostalnosti što nailazi na otpor veleposjednika i ljudi zadojenih talijanskim duhom. Borba talijanaša i narodnjaka bila je prisutna do početka I sv. rata. Za vrijeme austrijske uprave otok Pag postaje jedinstvena cjelina ali ostaje kolonatska ovisnost mnogih težaka prema rapskim gospodarima. Krajem 19. st. hrvatski jezik postaje službeni u školama I upravi. Uvode se brodske linije austrijskog Loyda tako da se u Novalji gradi riva za pristanak brodova.