Le prime tracce di frequentazione umana del territorio di Olbia risalgono al Neolitico Medio (4000-3500 a. C.), come testimoniano frammenti di ceramica da Porto Rotondo e soprattutto una statuetta femminile da S. Mariedda, che rappresenta la Dea della vita in forme opulente a sottolinearne la fertilità. Anche la successiva fase culturale, il Neolitico Recente (3500-2700 a. C.),offre scarsi resti, consistenti in pochi reperti ceramici e di ossidiana, il “vetro” di origine vulcanica ideale per la realizzazione di strumenti taglienti.Questi primi abitatori delle campagne olbiesi, stanziati qui per la presenza di aree fertili e riparati approdi, utilizzavano le cavità naturali scavate nel granito dai fenomeni atmosferici, i tafoni, per riparo e/o come luogo di sepoltura.
Nel periodo Eneolitico, pressoché unica ma sorprendente testimonianza sono le raffigurazioni umane schematiche della Grotta del Papa nell’Isola di Tavolara, databili verso il 2700-2500 a. C., realizzate in ocra rossa sulla parete destra dell’ingresso. E’ possibile che già allora la grotta fosse un luogo di culto come indicano i reperti archeologici più recenti lì rinvenuti.
Anche per la fase che precede immediatamente la Civiltà Nuragica, cioè l’Età del Bronzo Antico (1800-1600 a.C.), pochissimi sono gli indizi di frequentazione del territorio, ma tra essi è molto significativa la tomba collettiva a galleria di Su Monte de s’Ape, poi utilizzata anche dai nuragici con l’aggiunta di lastroni della facciata posti a semicerchio a realizzare così la tipica “tomba di giganti”.