Klub założony został 1 marca 1886r 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 1914r. 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 Nàstic spędził tylko 4 sezony w najwyższej klasie rozgrywkowej w Hiszpanii. W sezonie 1946–47 drużyna zajęła II 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 Barcelona. 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–07 klub pod wodzą Luisa Césara Sampedro powrócił po 56 latach do najwyższej klasy rozgrywkowej zajmując jednak 20, ostatnie miejsce oznaczające ponowną relegację do niższej ligi.
