The club was established at a meeting at the Bridge Hotel in December 1889. They joined the Senior Division of the East Sussex League in 1899 under the name "Newhaven & Cement Works". The club were runners-up in 1900–01 and again in 1903–04, before winning the Senior Division title and the Sussex RUR Cup in 1904–05. They then adopted their current name and went on to retain the league title in 1905–06. The 1908–09 season saw Newhaven win the title for a third time, but the league was then disbanded. The club joined the Mid-Sussex League and were champions in 1909–10 and 1911–12, by which time they had also rejoined the East Sussex League when it reformed in 1911. Following World War I, the club became members of Division One of the Brighton, Hove & District League in 1919–20, before becoming founder members of the Sussex County League in 1920. They won the Invitation Cup in 1948–49, and were Sussex County League champions in 1953–54. After finishing bottom of Division One in 1964–65, the club were relegated to Division Two. Although they were promoted back to Division One the following season, having finished as runners-up, the club were relegated back to Division Two again after finishing bottom of Division One in 1967–68. Newhaven were Division Two champions in 1971–72, earning promotion to Division One. Although they were Division One champions in 1973–74, just two seasons later they finished bottom of the division and were relegated back to Division Two. They went on to finish bottom of Division Two in 1977–78. After winning the Division Two title in 1990–91 the club were promoted to Division One. In 1993–94 they won the Sussex RUR Cup for a second time, beating Pagham 4–0 in the final. However, the club were relegated back to Division Two at the end of the 1994–95 season, and then relegated to Division Three after finishing bottom of Division Two in 1998–99. After thirteen seasons in Division Three, Newhaven won the division in 2011–12 and were promoted to Division Two; they also won the Sussex Intermediate Cup, beating Saltdean United in the final. The following season saw them finish as runners-up in Division Two, earning promotion to Division One. In 2014–15 they won the League Cup with a 3–1 win over Arundel in the final. In 2015 the league was renamed the Southern Combination, with Division One becoming the Premier Division. The club won the Sussex RUR Cup again in 2015–16, beating Chichester City 4–2 in the final, going on to retain the trophy the following season with a 5–0 win over Crawley Down Gatwick.
Ground
The club play at Fort Road. Redevelopment in the 1990s led to construction starting on a new stand. However, it was never finished due to the club's financial problems.
