The football club was first formed in 1976 by Charles Polson and Charles Head, the latter managing the team. A group of players associated to the old Police youth team called the "Blue Batons" and complemented by players that had been released by Glacis United and St Jago's joined forces to form the first Lincoln team that played in the Gibraltar fourth division as a youth team. The team was named after Lincoln City FC, who are nicknamed "the Imps", after a former Lincoln director sponsored them. When this Lincoln team became old enough to play Senior Football, it was decided to place the young team into the GFA second division. The team started to climb to the top in the second division in the season 1981–82 winning the league, the division cup and gaining promotion to the GFA's first division after only one season. The next year Lincoln finished in mid table in the first division. In 1983–84 Lincoln won the league and promotion to the Gibraltar Premier Division. In 1984–85 Lincoln played their first season in the Gibraltar Premier Division in which they were joint champions with Glacis United – the first of seven league titles which were won between 1984 and 1994. Lincoln won 14 Gibraltar Premier Division titles in a row from 2003 to 2016, bettering the previous record of nine in a row held by Glacis United in the 1960s. They also won the national treble of League, Rock Cup and Senior Cup in 2004, 2005, 2006, 2007, 2008 and 2011.
2014
In 2014, after Gibraltar had joined UEFA as the 54th member, Lincoln became the first Gibraltarian team to play in the qualifying stages of the UEFA Champions League. After claiming a 1–1 draw in the home match, they lost 5–2 at Faroese team HB and were eliminated in the first qualifying round.
In 2016 Lincoln pulled off a surprise victory against Scottish Premiership champions Celtic, with a 1–0 victory at home after a 48th-minute strike from Lee Casciaro in the club's second round match of the UEFA Champions League qualifying stage. The match was Brendan Rodgers first competitive fixture as manager of Celtic. The Glasgow side still comfortably qualified thanks to a 3–0 victory in the return leg at Celtic Park.
Seasons (since UEFA acceptance)
Stadium
Lincoln currently plays all league games at the 5,000-seat Victoria Stadium. The club share this ground with all clubs currently participating in the top two leagues in Gibraltar, the Gibraltar Premier Division and Gibraltar Second Division, as well as the Gibraltar Women's Football League, of which Lincoln also runs a team. Due to the ground's failure to meet guidelines in the 2017–18 season, Lincoln, along with Europa and St Joseph's, were forced to play their European competition matches at the Estadio Algarve in Portugal, while improvements were carried out on Victoria Stadium. It is expected that the ground will be renovated and expanded to a football specific stadium with a capacity of 8,000 by 2021.
Honours
Gibraltar Football League: 24
Rock Cup: 17
Pepe Reyes Cup: 11
Regional
Gibraltar League Senior Cup: 18
European record
Lincoln's first qualifying round match of the 2014–15 UEFA Champions League marked the first match played by a Gibraltarian club in UEFA competition. After converting a penalty, a second half goal was conceded and the game ended in a draw.
