W 1991 trenerem Nei Salamis został Jerzy Engel i dwukrotnie pod jego wodzą klub kończył rozgrywki na trzecim miejscu w 1993 i 1995. W 1995, 1997 i 2000 klub uczestniczył bez sukcesów w Pucharze Intertoto. Ostatnimi sukcesami Nei Salaminy było wywalczenie czwartego miejsca w lidze w 2000 oraz dotarcie do finału Pucharu Cypru rok później. W 2001 klub po raz drugi spadł do drugiej ligi. W pierwszej dekadzie jeszcze trzykrotnie Nea Salamis spadała do Protathlima B’ Kategorias w 2003, 2008 i 2010, zwykle szybko powracając do najwyższej klasy rozgrywkowej. Od sezonu 2011/2012 klub ponownie znajduje się w A’ Kategorias.
Sukcesy Puchar Cypru (1): 1990. finał Puchar Cypru (2): 1966, 2001. Superpuchar Cypru(1): 1990. trzecie miejsce w Protathlima A’ Kategorias: 1956, 1966, 1993, 1995. wygranie Protathlima B’ Kategorias: 1955, 1980, 2002, 2004.
Trenerzy w historii klubu Jerzy Engel (1991-1995, 1996) Momčilo Vukotić (1995-1996) Georgi Wasilew (2003) Andreas Michaelides (2005-2006) Panicos Orphanides (2003-2005, 2007-2008)
Europejskie puchary