Założony w 1976 roku Lincoln Red Imps jest najbardziej utytułowanym i rozpoznawalnym klubem piłkarskim Gibraltaru. Drużyna wyrosła na potęgę w lokalnych rozgrywkach, choć jej historia rozwijała się w realiach niewielkiego terytorium, gdzie futbol przez wiele lat miał półprofesjonalny charakter. Czerwone Diabły zdobyły dziesiątki mistrzostw Gibraltaru oraz wielokrotnie sięgały po krajowy puchar i superpuchar. Szczególne miejsce w klubowej tradycji zajmuje seria czternastu kolejnych tytułów mistrzowskich, zakończona w 2016 roku. Wynik ten przez długi czas uchodził za jeden z najbardziej niezwykłych rekordów w europejskim futbolu, a dominacja Lincoln sprawiła, że zespół stał się punktem odniesienia dla całej miejscowej piłki.
Przełomem w historii klubu był debiut gibraltarskich drużyn w eliminacjach europejskich po przyjęciu miejscowego związku do UEFA. W 2016 roku Lincoln Red Imps zasłynął zwycięstwem 1:0 nad Celtikiem w pierwszym meczu eliminacji Ligi Mistrzów. Gol i wygrana na własnym boisku przeciwko szkockiemu mistrzowi, prowadzonemu przez Brendana Rodgersa, były jednym z największych sukcesów w historii sportu na Gibraltarze. Rewanż zakończył się porażką Lincoln, ale triumf na stałe zmienił postrzeganie tamtejszych klubów. Kolejnym kamieniem milowym był sezon 2021/22, gdy Lincoln jako pierwszy zespół z Gibraltaru awansował do fazy grupowej europejskich pucharów, występując w Lidze Konferencji Europy. Klub opiera siłę na zawodnikach związanych z reprezentacją Gibraltaru, uzupełnianych piłkarzami z Hiszpanii, i pozostaje symbolem ambicji małej piłkarskiej społeczności. Domowe mecze rozgrywa na historycznym Victoria Stadium, położonym w cieniu Skały Gibraltarskiej.