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 trumpeteer 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).
Until the early 60s, 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 40 editions, being one of only five clubs never to have been demoted into the second division.