La storia di Gavoi è molto antica. Pare ormai accertato che si tratti di una colonia ebraica del IV secolo d.C., probabilmente proveniente dalla stessa Isola: nel I secolo d.C. i Romani avevano effettuato massicce deportazioni dall'attuale Medio Oriente, ed avevano creato (principalmente nel Campidano di Cagliari) colonie giudaiche in Sardegna, alcune delle quali si erano successivamente spostate verso località più favorevoli. Dell'età romana resta un ponte, oggi sommerso dal lago artificiale, mentre le numerose suppellettili di età romana, di cui si aveva notizia ancora sul finire dell'Ottocento, con buona probabilità sarebbero state oggetto di commerci archeologici clandestini. Della provenienza religiosa rimane invece il culto di Sant'Antioco, uno dei primi santi cui si riferivano le comunità ebraiche che per ovvi motivi di opportunità si convertivano al Cristianesimo. Lo stabilirsi di una comunità di un certo rilievo è confermato anche dalla costante presenza del toponimo nelle carte geografiche e dalle strade interne, di tracciato romano, che tuttora sono in uso e che non vennero quindi abbandonate o avvicendate. 

Intorno al Seicento, la rigogliosità dei boschi vi condusse diverse famiglie di carbonai (per lo più provenienti dalla Toscana, come del resto testimoniano i cognomi diffusi nel paese), che però non distrussero le vaste foreste, ed anzi ne utilizzarono solo una minima parte, principalmente intorno all'abitato. Con il commercio del legname e del carbone, giunse dal Continente anche l'architettura pisana, neo-romanica, di cui la parrocchiale di San Gavino è un notato esempio in graniti rosati.

Nel 1604 il paese fu annesso al Ducato di Mandas.
Il Settecento fu un secolo importante per la comunità locale, che grazie ai suoi poeti estemporanei cominciò ad essere sempre più conosciuta nel resto dell'Isola. La tradizione orale ha salvaguardato rime di numerosi autori che, nel confronto con quanto tramandato in altre aree sarde, testimonia la presenza di una produzione artistica corposa ed apprezzata.