От създаването си през 1948 г. до 1955 г. Неа Саламис играе във втора дивизия. Още в първия си сезон в първа дивизия отборът се класира на 3-то място на 4 точки зад шампиона АЕЛ. Неа достига най-добрите си класирания през сезоните 1955/56, 1965/66, 1992/93 и 1994/95. Саламина не е ставал шампион, но е бил много пъти близо до титлата. През сезон 1965 – 66 отборът играе страхотен футбол и достига дори финал за купата на страната. 70-те години са много лоши за Неа, тъй като на няколко пъти е много близо до изпадане. Най-лошото е през 1974 г., когато Саламина е принуден да напусне град Фамагуста, поради турското нашествие и окупиране на северната част на острова. Така отбора се премества да домакинства до днес в близкия крайморски град Ларнака. През сезон 1978/79 отбора изпада за първи път, но се завръща само година по-късно като шампион на втора дивизия. През 1990 г. Неа постига много успехи като побеждава Омония (Никозия) с 3:2 на финала за купата. В същата година отбора спечелва и суперкупата, побеждавайки АПОЕЛ с 1:0. Неа Саламис е играл още два финала за купата на страната (през 1966 и 2001), но и двата пъти губи от Аполон Лимасол. Първите четири години след 2000 г. са много лоши за отбора. Неа изпада два пъти за четири години, през 2001 г., въпреки че достига финал за купата и през 2003 г. Завръща се през сезон 2004/05 и се задържа до сезон 2007/08, когато отново изпада. Класира се отново за първа дивизия в последния кръг от сезон 2008/09, като завършва на 3-то място, което дава право на промоция.