Gil Vicente werd opgericht in 1924 door een groep vrienden en werd genoemd naar de gelijknamige toneelschrijver Gil Vicente. In 1990 wist de club voor het eerst te promoveren naar de Primeira Liga, de hoogste voetbaldivisie van Portugal. De Nederlandse aanvaller Remco Boere speelde in het seizoen 1991/92 voor de club, die destijds onder leiding stond van de latere bondscoach van Portugal, António Oliveira. In 1997 degradeerde de club weer. In 1999 werd dankzij het kampioenschap in de Liga de Honra opnieuw promotie bereikt, maar in 2006 degradeerde de club wederom. Dat was opmerkelijk, omdat Gil Vicente dat seizoen als twaalfde was geëindigd. De Portugese competitie werd ingekrompen van 18 naar 16 clubs, waardoor vier clubs degradeerden en de nummer vijftien van de ranglijst, Belenenses, wist met succes aan te voeren dat Gil Vicente gedurende het seizoen verschillende malen een niet-speelgerechtigde speler had opgesteld: de Angolees Mateus. In 2011 dwong Gil Vicente andermaal promotie af door weer het kampioenschap in de Liga de Honra te behalen. Het beste resultaat in de hoogste divisie is de vijfde plaats in het seizoen 1999/00.
Stadion
Gil Vicente speelt sinds 2004 haar thuiswedstrijden in het Estádio Cidade de Barcelos dat plaats biedt aan 12.734 toeschouwers. Voor die tijd werden de thuiswedstrijden afgewerkt in het Estádio Adelino Ribeiro Novo, waar tegenwoordig de jeugdteams van de club spelen.