The present club was founded as recently as the summer of 1998 following a merger between two separate local clubs : AFC Lymington of the Wessex League and New Milton Town of the Hampshire League.

Formed in 1898, New Milton FC competed at both Bournemouth and Hampshire League levels, playing for most of that time on the Recreation Ground just off the town centre; where the club eventually developed its own amenities. However, given the opportunity by the Town Council to relocate to a new site within the planned Fawcett's Field sports complex, the club changed its name to New Milton Town and moved there in 1993; in the process creating what were considered to be the best sports and social facilities in the New Forest area. This gave the club a base from which to pursue the aim of moving up to Wessex League football; but the necessary success on the field eluded them.

The reverse was the case on the Lymington side. Formed in 1875, Lymington Town FC had also enjoyed a long period of involvement at Hampshire League level playing at the town's Sports Ground, a facility which was shared with Lymington Cricket Club. When the Wessex League was formed in 1986, the club became one of the original participants but initially found the going difficult. In an attempt to consolidate, the club merged with local rivals Wellworthy Athletic in 1988 and became AFC Lymington, although still based at the Sports Ground. The new club gradually evolved into one of the most successful Wessex League sides, finishing as runners-up in the league in 1991-92 before securing their first Championship success the following year. Under the management of Derek Binns, the club again finished runners-up in 1995-96 and went on to claim their second Championship win the following season whilst achieving the remarkable feat of being the only senior side in the country to complete the league campaign undefeated. The title was successfully retained in 1997-98 and a move up to Southern League football seemed inevitable but for the fact that the club was not in a position to meet the more stringent ground requirements at that level.

The proposed solution was a merger with New Milton Town, with the new club being based at Fawcett's Field. With such long histories behind them it was inevitable that this idea would not be to everyone's liking but it was eventually agreed and the newly-constituted club came into being in the summer of 1998. Some disaffected members left and this led to the revival of Lymington Town FC who re-joined the Hampshire League and continue to compete at that level, while a new side was formed under the name of Milford & Milton to take New Milton's place in the Hants setup although they only completed one season and disbanded in 1999.

Continuing under Derek Binns' management, Lymington & New Milton carried on where AFC Lymington had left off. In their first competitive fixture in July 1998, the club beat Eastern Counties League champions Wroxham to claim the inaugural Jewson Champions Shield. The first full season was equally successful, with the club winning the Wessex League at the first attempt, giving Binns a third successive championship title. The club also achieved a best-ever performance in the FA Vase by reaching the Quarter-Finals, as well as Semi-Final appearances in the Hants Senior Cup and Russell-Cotes Cup and were beaten finalists in the Wessex League Cup, losing to Cowes Sports on penalties. Crucially, however, the hoped-for promotion to the Southern League did not occur because Fawcett's Field narrowly failed to meet the league's expanded ground-grading requirements.

In 1999-2000 the club scored more goals, gained a higher points total and lost fewer games than in the previous title-winning season but could only finish as runners-up in the league to Wimborne Town who took the title on goal difference. Beaten in the League Cup final by a single goal, also at the hands of Wimborne, the club gained some consolation by taking the Russell-Cotes Cup with a 2-0 final win against Eastleigh. This season also saw the club achieve a best-ever performance in the FA Cup, reaching the Fourth Qualifying Round before going out to Aldershot Town in front of over 1,500 spectators at Fawcett's Field, the merged club's largest attendance to date. With Wimborne unable to capitalise on their success by accepting promotion, the way was clear for L&NM to claim a Southern League place but, frustratingly, delays in achieving the necessary ground improvements in time meant that, once again, the opportunity was lost.

Season 2000-2001 began on an optimistic note, with the ground improvements having finally been carried out. Despite early reverses in the FA Cup and FA Vase, the team opened the league campaign with a run of ten straight victories. Then the weather set in and caused a huge backlog of postponed matches. In the midst of this the club's Executive Committee decided that, irrespective of league position, the club would not be pursuing the ambition of joining the Southern League and cited financial reasons for their decision. This was undoubtedly a blow to the team and to manager Derek Binns in particular, who shortly afterwards announced that he intended to step down at the end of the season. Long-serving player and club captain Graham Kemp was chosen as Binns' replacement. The situation was confused even further when it became apparent that talks about a possible merger had been held with Southern League neighbours Bashley. However, the club's executive eventually rejected the idea, a decision which resulted in Derek Binns' abrupt departure and Graham Kemp taking over in a player-manager role. Remarkably, considering all the off-field activity, the team worked its way through the fixture congestion resulting from the bad weather and managed to complete the league programme, once again finishing runners-up (with a best-ever points total) and also achieving a Semi-final appearance in the Hants Senior Cup.

After such upheavals it was, perhaps, inevitable that the team's performance would eventually suffer and the 2001-2002 season saw the club's on-field fortunes decline somewhat from the previous high level. Nevertheless, with Graham Kemp consolidating his management position, a respectable sixth place in the league was achieved as well as Semi-final appearances in the League Cup and Russell-Cotes Cup. Towards the end of the season, the team's management was expanded by the addition of long-time Wimborne manager, Alex Pike, as assistant to Kemp and during the close season these two set about reshaping the team.

With this augmented management structure in place for 2002-2003, a playing squad was assembled that was thought capable of challenging for league honours and thus potentially fulfilling the quest for Southern League football. Any remaining questions concerning finance appeared to have been answered when the team put the poor performances of the previous two seasons in the FA Cup behind them and embarked on an exciting run which had the added benefit of earning a considerable sum from the FA's enhanced prize-money allocation. After finally being eliminated by Crawley in front of a big crowd at Fawcett's Field, the team continued to perform well in both the league and the FA Vase. A notable victory was gained in the Vase competition when the team pulled off a remarkable extra-time win, after coming from behind, to beat Team Bath; a side who had already achieved nationwide attention by reaching the 1st Round proper of the FA Cup. Inevitably, this run of form caught the attention of clubs from the higher echelons and a number of the players found themselves being watched with a view to possible transfers. With other league contenders continuing to perform well, the team was forced to maintain a high performance level in order to remain in contention but a dip in form around the Christmas/New Year period put additional strain on the management team, determined as they were to achieve the 'ultimate goal'. When the club subsequently announced that there were still doubts about the financial viability of seeking promotion, the various pressures on and off the field came to a head. This was exacerbated further when the club chairman revealed that he had been approached by representatives of the Bashley club, who seemed interested in reviving the question of a merger, first raised two years before. Although this approach was soundly rejected by the club's executive, the various events had clearly undermined the confidence of the management and players. Graham Kemp felt himself to be in a compromised position and decided he had no option but to resign, despite efforts by the executive and players to convince him to stay on. With Kemp's departure, it was perhaps inevitable that players would consider their own positions, particularly with approaches being made by other clubs sensing the opportunity. Several key first-team members departed, leaving the remainder to struggle on under a temporary management regime. At the end of the season, with the future looking increasingly uncertain, most of the remaining first-team squad departed.

Despite this, the club has seized the initiative and appointed successful former Totton boss, Ian Robinson, as the new team manager. Robinson's former assistant at Totton, Richie Phippard, has also joined the club in the assistant manager's role. With additional help from former Brockenhurst manager Chris Collinge behind the scenes, Robinson has already set about building a first team squad almost from scratch. Already a number of talented and promising players have signed for the club - most notable of which, perhaps, is former AFC Bournemouth player and "Wembley Hero", John Bailey. So, it seems, a whole new chapter is about to open for the club with many of the past associations with players and staff being swept away, while a new and potentially exciting squad is in the process of being established for the future.