Enosis Neon Paralimniou was founded in April 1944, following the merger of two Paralimni clubs, Heracles and People's Love.
The club's emblem is the Parthenon, with a trumpeter and the year 1936 inscription, birth year of the club Heracles. The only reason why founders decided to adopt the year 1936 as the new club's birth year instead of the year 1944 has purely to do with Heracles official papers. On those, it was clear that whenever the club's members decided to cease its operations, all of its assets (movable and immovable property) would go straight to the Church. In view of that and in order to avoid any legal implications, the newly born club of Enosis was reckoned by the authorities as a continuation of the club Heracles of Paralimni, absorbing the other club, People's Love.
The first football match played in Paralimni took place in the first half of the year 1945, some weeks before the end of World War II, against a German team of POWs (no further details found). The first recorded encounter was on 16 September 1945, against a mixed team from Anorthosis and EHAN, both of Famagusta (a final 4–5 loss).
The team’s colours of claret and blue were introduced by the Parnerou brothers who were both supporters of West Ham United and acquainted with player Bobby Moore. Moore donated West Ham United kits for the team to play in 1971, 2 years after the team's promotion to the Cypriot First Division . These colours became an established part of the club itself.
Until the early 1960s, Enosis took part only in local competitions, since the Cyprus Football Association (CFA) had repeatedly denied its participation in its competitions, stating that only clubs based in towns could take part. The CFA's denial was the reason why Enosis joined E.A.P.O., a village-based club association. In 1965, the CFA changed its rules and Enosis finally managed to join and participate in the second division. From the very beginning, the side tried to win promotion to the first division and, after four attempts, managed to finish first, in the football season of 1968–69. Since then, Enosis has taken part in all 45 editions of first division, being one of only five clubs never to have been demoted into the second division until 2013–14, when it was relegated for the first time to the second division after finishing 13th in the league.
MSV Duisburg
Vasas
Beveren
Bregenz
Kyriacos Ttikkis
N'Jari Patterns
Giorgos Safaris
Svatopluk Pluskal (1971–78), (1983–85)
Vic Buckingham (1982)
Slobodan Vučeković (1993–96)
Angel Kolev (1998–99)
Nenad Starovlah (1999–00)
Eli Guttman (2004–06)
Čedomir Janevski (June 10, 2009 – Jan 10, 2011)
Saša Jovanović (July 1, 2013 – Oct 11, 2013)
Carit Falch (Nov 29, 2018 – Apr 23, 2019)
Gustavo Siviero (Sep 30, 2019 – Jan 20, 2020)
Carlos Alós (Sep 21, 2020 – Apr 11, 2021)