Poche le testimonianze relative ad una frequentazione in età preromana e romana della zona. Il nome del paese è riportato nei documenti medioevali in varie forme: "Petre Sturmine", "Petrastrumula", "Petra Strumini", "Petrae Strumiliae" e "Petra Sternina".
La prima notizia storica risale al 774, anno in cui il principe longobardo Arechi II diede alla chiesa di S. Sofia in Benevento il castello di Pietrasturminea.Evidentemente il primo borgo dovette svilupparsi proprio durante l'età longobarda ai piedi della fortezza edificata sulla guglia rocciosa dalla quale si dominava parte del territorio circostante. Nel 971 alcuni possedimenti del feudo furono concessi da un Guaidernando all'arcivescovado beneventano, mentre al 1102 può ricondursi un altro atto di donazione in cui si fa menzione delle chiese allora ubicate nel borgo e di proprietà del Monastero di S. Sofia.Durante la dominazione sveva (1194 - 1266) Pietrastornina era sotto il diretto controllo imperiale e solo durante il governo di re Manfredi entrò in possesso di Riccardo Filangieri. Dopo la battaglia di Benevento il feudo passò al Regio Fisco e Carlo I d'Angiò ne fece dono nel 1270 al provenzale Guglielmo Stendardo. Dopo la sua morte ne citarono le terre il primogenito Guglielmo II, Maresciallo del Regno di Sicilia e dal 1302 Gran Contestabile del Regno, ed il terzogenito Tommaso Stendardo (1309). Nel 1338 barone di Pietrastornina era Amelio Del Balzo, Giustiziere della Provincia di Terra di Lavoro, a cui successero nel 1351 la figlia Ceccarella e nel 1348 Matteo della Marra. Passato a Filippo Caracciolo, Maresciallo del Regno, il paese fu preso con la forza nel 1418 da Marino della Leonessa, signore di Cervinara. A costui fu tolto dalla regina Giovanna II, che nel 1426 lo diede nuovamente al legittimo possessore. Ma dal signore di Cervinara, che lo ricevette comunque in dote dalla moglie Novella Caracciolo, il feudo fu venduto per circa mille ducati al fratello Giacomo della Leonessa, con assenso regio dell'11 aprile 1450, da cui lo ebbe nel 1461 Fabrizio. Durante il regno di Ferdinando I d'Aragona Pietrastornina fu acquistata dal conte di Maddaloni, Diomede Carafa, alla cui famiglia il feudo appartenne con Giovanni Antonio (1487) e Alfonso Carafa (1567), conte di Montoro. Con l'avvento della dominazione spagnola in Italia meridionale, il paese venne acquisito nell'ottobre del 1586 dal nobile Cesare Pagano, al quale successe nel 1599 il primogenito Ugo. Venduto nel 1630 per ventottomila ducati a Vincenzo Cossa, fu da questi alienato cinque anni dopo ad Andrea Lattiero, che lo tenne dal 1643 con il titolo di principe di Pietrastornina. Morto nel 1644 senza lasciare eredi, tutte le sue proprietà furono confermate fino all'eversione della feudalità rispettivamente ai discendenti Nicola (1644), Marcello (1646), Antonio (1692), Tommaso (1720), Antonio II (1730), Tommaso II (1778), Antonio III e Giuseppe Lottiero (1831).