The club is named after the ancient city of Cyprus, Salamis or Salamina, which is located nearby modern Famagusta ("Nea" means "new" in Greek language).

[5] In early 1947 a group from Famagusta (including leftists, members and non-members of GSE and Anorthosis) concluded there was room for another sports club in the city.

[8] Before the Pancyprian Games in May 1948, the Hellenic Amateur Athletic Association (SEGAS) asked all gymnastics associations in Cyprus, their members and athletes, to sign a public declaration that would express their support to the rightists in Greek Civil War, to declare that they espoused "nationalist beliefs" and to repudiate the leftists.

[9] The left-wing athletes decided to support the Kinyras Paphos association if the decision to exclude it from the Pancyprian Games stood.

The GSZ amended its constitution, prohibiting enrollment of new members unless they signed a declaration that "they espouse the Hellenic nationalistic ideals".

[15][16] Six teams belonged to the CAFF: Nea Salamina in Famagusta, Omonia and Orfeas in Nicosia, Alki at Larnaca, AMOL at Limassol (renamed Antaeus in 1951) and Neos Asteras in Morphou.

In August of that year Nea Salamina, Omonia, Alki and Antaeus submitted a joint application to the CFA to join the Cypriot First Division.

They initially practiced at the Saint Lukas pitch (Proodou) in Famagusta[16][24] and began efforts to build a privately owned stadium.

In December 1948 Israel made a CYP£3,000 donation to the city of Famagusta, in gratitude for aid by its inhabitants to Jewish refugees, for a community-service project.

Gabriel Makris, a Famagusta alderman and Nea Salamina footballer, supported the association's recommendation to build the stadium.

The stadium is named for the town of Famagusta (Greek: Αμμόχωστος; Ammochostos), the original home of Nea Salamina before the Turkish occupation, and was built in 1991 near the refugee camps.

[32] In five leagues of the Cyprus Amateur Football Federation, Nea Salamina failed to win a title; during its last two years, it finished second.

[38] During the same period, in the 1954–55 Cypriot Cup, excluded from subsequent phases one of the strongest teams of the season, APOEL with 3–2 win in GSE stadium.

[39][40][41] After 57 years, in the 2001–02 Cypriot Cup the team repeated this success; after struggling in the second division, it defeated future champion APOEL F.C.

[50] In December 1963, the league disbanded; at that time, Nea Salamina was in a tight three-way race with Omonia and APOEL.

[57] Near the end of the 1966–67 season the board of Olympiakos reported rumors of future match-fixing between Nea Salamina and Anorthosis to the team, which its president denied.

Although board members were uncertain whether Nea Salamina should play (due to the refugee problem), they decided to participate so the team could remain in the Cypriot First Division and stay alive.

[69][70] In the summer of 1974, before the Turkish occupation, Nea Salamina signed Bulgarian coach Iancho Arsov, who went on to win titles with Omonia decades later.

The agreement was canceled when financial problems caused by the team's refugee status made it impossible to pay for a foreign coach.

[75] For the 1981–82 season, Nea Salamina acquired foreign footballers for the first time, Bulgarians Nazca Michailiof and Stefan Pavlov.

The linesman, claiming to have received blows, was transported to the hospital where radiographs failed to show injuries caused by the players.

The players remained in jail for five days and were released after public outcry, but then CFA authorities imposed crippling sanctions on them, ordering them to stay off the court for several months.

During this period, Nea Salamina's player Nigel Maknil was named the league's top scorer, with 19 goals.

[82] The 1989–90 season was the most successful in the history of the team when Nea Salamina won its first football title, the Cypriot Cup.

[87][88][89][90] Salamina went on to take its second title in only a few months, the LTV Super Cup Shield,[85] against rival APOEL, 1–0, at Makario Stadium, the opponents' home ground.

[6][94][96] Lineups for the two games were Christakis Christofi, Artemis Andreou, Kipros Tsigkelis, Elissaios Psaras, Floros Nikolaou, Kenny Dyer, Pambis Andreou, Takis David (replaced by Stavros Efthymiou in the 68th minute), Nigel Maknil (replaced by Christakis Mavros in the 85th minute), Elias Elias and Vangelis Adamou (home),[95] and Yiannakis Ioannou, Andreas Artemis, Kipros Tsigkelis, Elissaios Psaras, Floros Nicholaou, Kenny Dyer, Vangelis Adamou, Mavros Christakis, Nigel Maknil (replaced by Pambis Andreou in the 47th minute), Elias Elias and Vassos Mavros (away).

Nea Salamina easily won over Digenis, but Doxa also defeated Apollo and Ethnikos Achna's match with Enosis Neon Paralimni FC resulted in a draw.

In the 2000 UEFA Intertoto Cup, the team qualified for the second round, with two victories against the Albanian KS Vllaznia Shkodër, but were eliminated in Vienna by Austria Wien, 3–0.

About 2,500 fans sat together in the stands, and the match was attended by political leaders, local sports authorities and representatives of the Church of Cyprus.

In 2008–09 (when it also finished second), it forfeited the championship game (at home, against Apollon Limassol) when the referee stopped the match due spectator overcrowding.