Non si hanno notizie certe sulla fondazione del paese perché non si ha nessun documento che ne attesti la nascita. Si ricordano però varie leggende come quella che narra che il paese fu fondato dalle popolazioni costiere che si spostarono all’interno per sfuggire alle incursioni saracene oppure quella secondo cui gli abitanti dell’altopiano di Ósono, situato a 3 km da Triei, scesero a valle per salvarsi dalla peste fondando un nuovo paese. Per quanto riguarda l’origine del nome Triei, si pensa che derivi da Tereiu, luogo ricco di ginestra: in primavera infatti le colline si colorano del giallo intenso dalla ginestra in fiore che abbonda in questi luoghi. In sardo infatti questa pianta è chiamata Terìa. Ci sono però altre ipotesi secondo cui Triei deriverebbe da Trisei, ossia paese formato da tre piccoli villaggi.
Nel 1316 compare per la prima volta il nome Triei in un documento concernente le rendite pisane delle curatorie di Sarrabus, Tolostra, Chirra e Ogliastra, facenti parte dell’antico Giudicato di Cagliari. Come gli altri paesi ogliastrini passò poi a far parte del Giudicato di Gallura; dal primo decennio del secolo XIV passò sotto il domino pisano, dal 1323 agli Aragonesi, dal 1479 agli Spagnoli, dal 1708 all’Austria, dal 1720 ai Piemontesi, dal 1861 all’Italia. Nell’altopiano di Osono, a pochi chilometri dall’abitato, anticamente sorgeva un villaggio, chiamato appunto Osono, sicuramente precedente allo stesso Triei, citato in un documento che risale alla fine del periodo giudicale (1227) dove si fa riferimento ad una serva chiamata “Maria Locci, ankila de la villa de Osono”. Sulla scomparsa di questo villaggio così come per altri che hanno subito medesima sorte, non si hanno notizie certe ma solo leggende tramandate oralmente.