The club formed in 2013 amid the heightened interest in football on Gibraltar, after the territory was admitted to UEFA that year. In their debut season in the Gibraltar Second Division, they finished 3rd and narrowly missed out on promotion. However, the club failed to improve on their debut season as a 7th place finish followed in 2014–15, a 5th place finish in 2015–16 and a 6th place finish in their final season under English manager Gary Turner-Bone.

The summer of 2017 saw significant changes at the club as it was taken over by Nigerian businessman Sunday Adeleye, who also owns DSS F.C. of the Nigeria National League. Aside from establishing a link between the two clubs with young players transferring between DSS and Olympique, the newly re-branded club hired Scottish manager Lewis Fraser and completely overhauled the squad, bringing in several players from his old club Angels F.C. along with assistant manager Steven Gallagher. The club's ambitions were made clear with the signing of 2 former international players throughout the 2017–18 season, including goalkeeper Jordan Perez and striker Robert Montovio in the summer.

The club endured a slow start to the season, struggling in mid-table by the winter break. This resulted in a large scale rebuild of the squad in January, exemplified by the loan addition of Lincoln Red Imps attacker Kyle Casciaro along with Godwin Egbo, Dizza Usman and Uche Nwankwo from parent club DSS. The expulsion of promotion rivals Angels on 2 February 2018 saw the club propelled from 4th to 2nd in the league, one point off unbeaten leaders Europa Point, without kicking a ball over the winter break. Accompanied by a club record 16–0 victory over mid-season league leaders Cannons on the penultimate matchday, Olympique guaranteed their spot in the promotion play-off on 20 May, after a late Max Bothen goal secured a 1–0 victory over Hound Dogs. However, they lost the play-off to Lynx on 8 June. At the end of the season, Fraser left the club, and the club appointed former Leo manager Norberto Alonso Simón on 13 July 2018.

As of 16 February 2019

Note: Flags indicate national team as defined under FIFA eligibility rules. Players may hold more than one non-FIFA nationality.

• Best League finish: 2nd, Gibraltar Second Division (2017–18)
• Best Rock Cup performance: Quarter-Finals (2017–18, 2019)
• Record victory: 16–0 vs Cannons, 8 May 2018

• Official website  
• F.C. Olympique 13 on Twitter