The band was named, at Harwood's suggestion, after a reptile from his native New Zealand.
The band was formed in 1996 by R.E.M.'s Peter Buck (guitar), Barrett Martin of the Screaming Trees (drums and percussion), Justin Harwood of Luna and The Chills (bass guitar, double bass), and Skerik of Critters Buggin (saxophones).
Originally a project to get musician friends some soundtrack work, the project evolved into an active band, doing occasional live shows, and recording their first album Breaking the Ethers, encompassing a sound influenced by various styles of music, from Lebanese and Asian music to more traditional Western folk music.
The band expanded in 1998, adding guitarist Scott McCaughey on guitar, Steve Berlin on saxophone and flute, Craig Flory on clarinets and saxophones, Elizabeth Pupo-Walker on congas and other percussion, and Mike Stone on drum kit; with Stone now on drums, Barrett Martin focused more on vibes and marimba. This expanded line-up released Trading With the Enemy, which added more exotic instrumentation while sticking to the familiar formula of borrowing from a variety of styles.
The band had eleven members at the time of 2001's Cinemathique, which was intended to fulfill the original desire of creating music for soundtracks. A remix album, The Loading Program, was released in 2003.
McCaughey and Buck are also permanent members of The Minus 5, and Martin has contributed to their performances and recordings as well.
- Breaking the Ethers – Epic Records – April 1997
- Trading with the Enemy – Epic Records – June 1998
- Cinemathique – Fast Horse Recordings – December 2001
- The Loading Program – Fast Horse Recordings – September 2003
- East of the Sun – Fast Horse Recordings – June 2007
- West of the Moon – Fast Horse Recordings – October 2007
- The Here and the Gone with Coleman Barks – Fast Horse Recordings – November 2008
- Underworld, August 2014
- "Pearl Jam and REM side-project Tuatura announce new album". Complete Music. Retrieved 19 June 2014.