I dati sulla nascita di Novoli sono incerti e confusi. Secondo alcune ipotesi Novoli sorse in seguito all'allontanamento della popolazione del casale di Porziano dal terreno paludoso, dove questo casale era appunto ubicato, nella contrada di San Nicola, per emigrare verso il terreno in cui oggi sorge Novoli. In questa area c'erano anticamente tre chiese vicinissime tra loro: dedicate al Salvatore, a San Giovanni, e a Santa Maria Madre del Signore; tutte e tre furono accorpate in una al momento della fondazione di Novoli, e divenne la chiesa matrice della comunità di Santa Maria Nova.
Grazie a delle ricerche recenti si sono trovati reperti in agro di Novoli relativi ad uno stanziamento umano del Medioevo. Nel 1872 sono state rinvenute ossa fossili del Pleistocene superiore e selci scheggiate del neolitico. Nel 1939 sono stati scoperti un menhir e una specchia a circa 2 Km dall'attuale centro. Al 1935 risalgono invece due tombe a Villa Portaccio del VI secolo a.C..
Sono scarse le informazioni che si hanno sul periodo del feudalesimo di Novoli, una famiglia feudataria importante fu quella dei Mattei; poco si sa su chi la precedette. Comunque con molta probabilità nulla di significativo fu fatto prima dei Mattei, nulla indica il potere o l'agire di famiglie precedenti a questa. Il segno dei Mattei invece è rimasto evidente, essi vissero abitualmente a Novoli. Il primo Mattei a reggere Santa Maria de Novis fu barone, Paolo; comprò la prima parte del feudo nel 1526, la seconda e ultima parte fu acquistata successivamente.
Il barone Mattei fece subito erigere il palazzo baronale. Il successore e figlio Filippo I, nel 1551 fece costruire un monastero dedicato alla Santa Maria delle Grazie, nonché la vicina chiesa di Sant'Onofrio, divenuta poi la tomba di famiglia. L'esponente di maggior prestigio della famiglia Mattei fu però Alessandro II, che si fece protettore di un gruppo di intellettuali e artisti. Alessandro III fu invece l'ultimo della famiglia Mattei.
All'inizio del 1700 i Carignani successero ai Mattei fino alla fine del feudalesimo, nel 1806. Fino al 1860 lo stemma di Novoli aveva come soggetto la Madonna di Costantinopoli con Gesù Bambino in grembo. Segno della devozione Mariana che ha influito anche sul nome del paese.