De club werd opgericht in 1999 als Clube Atlético Tocantinense. In 2002 speelde de club voor het eerst in de hoogste klasse van het Campeonato Tocantinense en werd daar laatste. De volgende jaren eindigde club in de lagere middenmoot. In 2006 werd de naam gewijzigd in Tocantins FC en werden de zwart-witte clubkleuren in blauw-wit gewijzigd. In 2008 bereikte de club de finale om de titel en won deze tegen Gurupi waardoor ze voor het eerst kampioen werden. In 2009 mocht de club dan deelnemen aan de Copa do Brasil, maar werd meteen uitgeschakeld door Atlético Paranaense. Ook in de Série D werd de club in de eerste ronde uitgeschakeld. De club kreeg met financiële problemen te kampen en een jaar na de titel volgde al een degradatie.
