Paternopoli ha radici che risalgono all’epoca preromana. Secondo alcuni studiosi la presenza di insediamenti umani nell’attuale territorio del comune può farsi risalire dal secolo VIII a.C. e la colonizzazione del territorio da parte dei Sabini alla fine del V e principio del IV sec. a.C.. Alcuni ritrovamenti archeologici, in particolare nelle contrade Casale e S. Pietro, fanno riferimento al periodo IV-III sec. a.C. fino all'età romana: si tratta di ruderi di ville e sepolcreti dai quali fu recuperato abbondante materiale archeologico come monete, ceramiche e iscrizioni varie. Nel corso della III guerra Sannitica, nel secolo III a.C., l'insediamento sabino fu raso al suolo dalle legioni romane vittoriose che consolidarono la propria presenza edificando, in località Sant'Andrea, un centro fortificato, in costante espansione fino alla metà del IV secolo d.C. Il territorio divenne nel tempo un rifugio di veri e propri eremiti detti “Pater” che, complice anche la crisi economica e demografica dovuta alle pestilenze e ai terremoti, scelsero questi luoghi per loro dimora, divenendo riferimento importante per la povera gente del luogo. La collina su cui si era insediato il Pater venne denominata "Paternum". La caduta dell'Impero romano comportò una rapida decadenza del territorio per effetto delle incursioni dei Vandali (455), degli Ostrogoti (495) e dei Goti (545), fino all'occupazione longobarda che, a partire dal 570, vi ripristinò condizioni di stabilità, seppure improntata a livelli di estrema miseria. Dopo il crollo dell'impero romano e la venuta dei barbari il territorio riprese così vita al termine del VI secolo sotto i Longobardi che giunsero nell'attuale territorio di Paternopoli all’epoca suddiviso in Bovianum (terre ad occidente del crinale lungo la direttrice Serra-San Quirico-Pesco Cupo), in Taurum (terre ad oriente del crinale citato), Caesinula (versante boschivo a ridosso dell'intero basso corso del Fredane), Paternum (sede dell'antico eremo del Pater). Sulla sommità della collina di Paternum venne realizzato un semplice accampamento (Fara) protetto da una palizzata di legno, che faceva capo ad una famiglia di guerrieri (arimanni).

Un nuovo atteggiamento non ostile da parte dei Longobardi verso la Chiesa favorì la nascita nel territorio di monasteri, a cui vennero concessi benefici fiscali, privilegi, donazioni che aiutarono la ripresa economica: le locali chiesette di San Pietro e di San Quirico ne trassero vantaggio divenendo punto di riferimento per i contadini del posto. Anche l'originaria Fara sul colle Paternum, da fortilizio militare si trasformò in "sala", cioè residenza con proprietà del feudatario dei terreni, pascoli e boschi limitrofi. Con il trattato di Ceprano del 1080, che pose fine alle lotte tra Longobardi e Normanni il territorio di Paternopoli divenne di proprietà di Roberto d'Altavilla. I Normanni favorirono la ripresa economica ed eressero, tra la fine dell'XI e l'inizio del XII secolo, il castello. Esso aveva una porta verso meridione, nel luogo dove sorgeva il fortilizio longobardo, approssimativamente dove oggi si trovano la torre campanaria e la piazzetta denominata "Scala Santa". Nell'anno 1139, il feudo fu assegnato in premio al signore di Gesualdo, Guglielmo, figlio illegittimo di Ruggero Borsa, duca di Puglia. Seppure coinvolta nelle lotte di potere che caratterizzarono il tardo medioevo, la posizione geografica dominante le valli del Fredane e del Calore, che le consentiva il controllo delle vie di transito per la Lucania e la Puglia, favorì la crescita economica e demografica dell'antica Paternopoli. Nel conflitto che vide contrapporsi l'aragonese Ferdinando I, legittimo re di Napoli, ai Francesi del duca Giovanni d'Angiò, pretendente al trono, l'antica Paternopoli ebbe un ruolo determinante al punto che il vincitore re Ferdinando, sul finire del 1400, avvertì l'esigenza di dotarla di un avanzato sistema difensivo, la cui torre si è conservata quasi integra fino ai principi del 900. Tra i feudatari che si sono succeduti nel tempo ricordiamo i De Capua , i Filangieri, i Caracciolo, i i Ludovisi, i Mirelli ed i Carafa d'Andria, ultimi Signori fino all'abolizione dei diritti feudali (1806). Sul finire del XVI secolo si costituì in Paterno una confraternita votata al culto di Maria Santissima della Consolazione. La devozione alla Vergine non si affievolì durante la peste del 1656 che ridusse drasticamente la popolazione, e tanta fede fu premiata con l'elargizione di una serie di eventi miracolosi che si manifestarono a partire dal 16 aprile 1751. Il XVIII ed il XIX secolo furono caratterizzati da un profondo fermento culturale. A Paterno si affermò una apprezzata "Scuola di lettere ed arti" ed uomini di elevata cultura contribuirono alla costituzione dell'unità d'Italia. Il borgo venne chiamato "Paterno" fino al 1863 (da cui "Patierno" in dialetto): la parola "Paternopoli" nell'etimo latino-greco significa Città (polis) del padre (Pater).