Le village naquit comme forteresse pour ceux qui avaient fui la côte devant les incursions sarrasines : un historien d'Oriolo, écrivant en 1695, raconte que ces populations se retirèrent «sous le rocher», s'établirent au lieu-dit Ravita puis bâtirent des maisons à plusieurs étages, qu'elles ceignirent de murs crénelés. On voit le nom changer de forme dans les documents : en grec byzantin c'est le kastron Ourtzoulon, puis Ourzoulon en 1117, Ortzoulon en 1131, Orgilon en 1132, Orghiolon en 1186 et enfin, dans une donation de Frédéric II de 1221, le latin Ordeolum. Gerhard Rohlfs l'a fait remonter à hordeolus, le grain d'orge. Vers l'an mille, Oriolo était déjà une civitas avec son propre notaire : un acte de 1015 s'achève par «souscrit par moi Leone, notaire de la ville d'Oriolo».
En septembre 1117, Mabilia, comtesse d'Oriolo, donna à l'abbaye de Cava une église avec ses fermes ; en 1129 le roi Roger assiégea le bourg et le prit ; et le vingt-quatre avril 1221 Frédéric II donna une grande forêt de ce territoire aux cisterciens de Santa Maria del Sagittario — en 1679, plus de quatre siècles plus tard, des citoyens d'Oriolo payaient encore la redevance foncière pour ces terres au commendataire de l'abbaye. En 1246 le fief était tenu par Ruggero De Amicis, l'un des plus hauts fonctionnaires du royaume et, à la fin, Grand Justicier : il échangeait vers et ballades avec Rinaldo d'Aquino et appartient à l'École sicilienne, et il prit part à la conjuration contre ce même Frédéric II qui avait donné la forêt. Le complot fut découvert, ses biens confisqués, et ce n'est qu'après sa mort que son fils fut réintégré dans la baronnie. Les registres angevins de 1276 comptent mille vingt-cinq habitants.