Beira-Mar was founded on 1 January 1922, and first reached the first division 39 years later, only lasting one single season. Until 1980 it would make a few further appearances in the top flight, the longest spell being from 1971 to 1974; in the 1976–77 campaign, former S.L. Benfica and Portugal legend Eusébio played briefly for the side, often being injured as the campaign ended in relegation.
As the UEFA Cup Winners' Cup was discontinued in 1999, Beira-Mar participated in the 1999–2000 UEFA Cup, losing 1–2 on aggregate to Dutch team Vitesse. In the domestic league the club finished in second position in the second division and immediately returned to the top flight. On 23 February 2002 Beira-Mar achieved a 3–2 away win against Porto, which was managed by a young José Mourinho: it would be the last home defeat for the manager for the following decade.
The return of Mário Jardel to Portugal to play for Beira-Mar was one of the biggest news in Portuguese football in the summer of 2006, as the 33-year old and former European Golden Shoe winner signed a one-year contract. The Brazilian scored in his official debut, a 2–2 home draw against Desportivo das Aves, but gradually lost his importance in the team, leaving in the following transfer window to a team in Cyprus; Beira-Mar would eventually be relegated, in a campaign which also included the sacking of manager Carlos Carvalhal and his replacement with Spaniard Francisco Soler, after the team signed a cooperation deal with Inverfutbol, a Spanish-based sporting company.