The club was originally formed in 1988 when a group of players left the youth team Plymouth Kolts and joined the Plymouth & District League in Division 4. In that same year the club secured sponsorship from Exeter Airport, and as part of that deal they changed their name to Ex-Air Flyers. They were the first club in Plymouth to be sponsored from outside the city limits. The club colours of yellow and blue are from the colours of the airport logo and remain the same today.
In their first season the club gained promotion and then moved the Parkway Sports Club. The club carried on to be promoted in successive seasons until it reached Division one and was waiting to join the Premier Division when the Devon League was formed in 1992. The club decided to apply to become members of the Devon League instead as the Parkway Sports Club had sufficient facilities to join the league. The club was accepted into the league but the club had to change its name so they become known as EAF Plymouth FC.
Before the 1993–94 season the Sports Club offered a number of extra facilities and help to the club, so the club changed their name to Plymouth Parkway FC. Five seasons later in 1998 the club left the Devon league to join the South Western League. On the eve of the 2000–01 season the club became homeless with the loss of the Parkway Sports Club due to a disagreement over the terms of the lease and subsequent maintenance costs. As a result, and with special permission from the league, the club spent that season having to play all of its games away from home. During their build up to the 2001/02 season the club announced they would be developing an area of Manadon as their new ground, to be known as Bolitho Park. While work was being completed, with controversial assistance from Plymouth City Council, they used The Brickfields athletics ground in Devonport, before they moved to their new and current home in August 2003.
In the 2006–07 season the club entered the FA Vase for the first time, making it to the second qualifying round in their first attempt. A season later the club became founding members of the South West Peninsula League, when the South Western Football League and the Devon County Football League merged. The club has remained in the premier division of the South West Peninsula League ever since.
The identity of the football club has been built on the drive to improve and progress on and off the pitch! Having spent nearly 20 years in the South Western leagues, at the end of the 2015/16 campaign the club’s officials decided that they wanted to put a plan together to move even further up the football pyramid. In order to achieve that goal, it was identified that Plymouth Parkway as a business were missing a few things. Subsequently, it was a busy summer before the 2016/17 season – the result of which Plymouth Parkway merged with another ambitious Plymouth football club formally named as Bar Sol Ona! Bar Sol Ona, who were challenging for promotion in the Plymouth and District Premier Division at the time, became Plymouth Parkway’s reserve team and moved to the East Cornwall Premier League Division One. Their under 18’s became Plymouth Parkway’s under 18’s. Off the pitch, Bar Sol Ona’s Chairman, Mark Russell, became the new Chairman of Plymouth Parkway and their first team manager, Andy Notman, became Parkway’s General Manager. Plymouth Parkway’s former Chairman, Jim Parsons, became Club President and former General Manager, Gez Baggott, became the Vice President! The merger and the new faces brought with it a fresh drive and ambition for the club to progress – not to mention stronger financial capabilities. The six members of the board (including long-term Club Secretary Genny Turner and Treasurer Brian Martin) made their intentions known immediately by applying for promotion to the Toolstation Western Football League.