In 1964 Eddie Wardell organised a group of boys, one of which was his son, to play football out of Palm Beach and compete in a three team football competition against Kingscliff and Twin Towns. The first game for Palm Beach was held at Salk Oval and the team members wore plain green T shirts but the team would later move to a council paddock also located in Palm Beach. By 1965 the local Gold Coast Association football competition wanted a presence in Palm Beach and invited the team to join the local junior competitions. The first official playing strip was debuted in 1965 which was a plain T shirt that embossed with a single blue stripe.
In 1966 the team incorporated three teams; under 8s, under 10s and under 12s. During sign on time it was decided the team needed to unofficially become a club and held its inaugural meeting in the Currumbin RSL. Neville Cripps, a father of a Palm Beach player, was elected the first president and names for the club began being thrown around. Names such as Palm Beach Hotspurs and Palm Beach Pilchards were put forward at the meeting but Palm Beach Currumbin Soccer Club was voted the winner. In 1966 the club began wearing playing strip which was a white shirt emblazoned with a large blue vee.
1971 saw the council reclaim the playing field of the club and urgent calls to council were made which led to a field behind the Tugun Bowls Club becoming their new home ground. With the team being located in Tugun their official name was changed to the Palm Beach Currumbin Tugun Soccer Club. The following year while John Neumann was developing the suburb of Palm Beach he suggested to the club that they should attempt to be given two recreational fields in Mallawa Drive, Palm Beach. Club president Mal Sutherland met with the council which would eventually lead to the club being given two fields at their present location on Mallawa Drive. The Palm Beach Currumbin Lions Football Club donated the blue and white striped strip that the club would begin wearing.
The Gold Coast Association decided in 1975 to begin a senior football competition and the following year Palm Beach would enter their first senior team. By 1977 the building of a clubhouse began as well as the installment of the floodlights which allowed the club to hold night training sessions. In 1979 a club meeting was held which resulted in the decision for the club to become the first soccer club on the Gold Coast to register as a limited company. 1979 also saw Palm Beach enter an under 16s team in the Brisbane South competition in an attempt to attract higher quality players to begin playing on the Gold Coast and more specifically at Palm Beach. 1983 saw the additional of more floodlights which allowed the club to host night matches as well as the club introducing the shark as the emblem and officially become the Palm Beach Sharks.
In June 1992 the club was granted a full license by the Licensing Commission which allowed the Sharks apply and be given permission to install poker machines. Thirty year anniversary celebrations took place for the Sharks in 1997 at the Currumbin RSL, the venue in which the club held their first meeting 31 years earlier. In 2000 the Sharks were invited to compete in the Brisbane-based State League. The Sharks would prove their worth in 2005 by capturing the minor premiership, the premier cup as well as finishing runner up in the championship. In 2008 the club would withdraw senior teams from all Brisbane competition due to a lack of funds. In October 2012 it was announced that Football Federation Australia granted the Palm Beach Sharks a five year license into the newly formed Australian Premier League Queensland Conference along with teams from Brisbane, Moreton Bay, Rockhampton, Sunshine Coast and Townsville.