Klub założony został 1 marca 1886 przez grupę kilkunastu ludzi chcących promować gimnastykę oraz rozwój sportu w mieście. Z początku klub rozwijał sekcję boksu, kolarstwa oraz szermierki. W 1914 powstała oficjalna sekcja piłkarska Club Olímpic de Tarragona rozgrywająca swoje mecze na stadionie Avenida Catalunya, aż do roku 1972 kiedy to drużyna przeniosła się na obecny obiekt Nou Estadi.
W swojej historii Gimnástic spędził tylko 4 sezony w najwyższej klasie rozgrywkowej w Hiszpanii. W sezonie 1946/1947 drużyna zajęła 2. miejsce w Segunda División i po raz pierwszy awansowała do Primera División. W tym samym sezonie klub dotarł do półfinału Pucharu Króla eliminując w ćwierćfinale FC Barcelonę. W półfinale Nàstic przegrał w dwumeczu z innym klubem z Barcelony - RCD Espanyol 5:4, osiągając jednak swój najlepszy rezultat w historii tych rozgrywek.
W latach 1951–2005 klub występował w Segunda División, Segunda División B oraz Tercera División. Dopiero w sezonie 2006/2007 klub pod wodzą Luisa Césara Sampedro powrócił po 56 latach do najwyższej klasy rozgrywkowej zajmując jednak ostatnie, dwudzieste, miejsce oznaczające ponowną relegację do niższej ligi.