Olympic was founded in 1967 under the name Pan Rhodian. The following year the club joined the Queensland Soccer Federation, changing its name to Brisbane Olympic United as a condition of joining the federation. In 2008, the club again changed its name to Olympic FC upon joining the Queensland State League (QSL). After playing in the QSL in 2008 and 2009, the club elected to play in the Brisbane Premier League for the 2010 season. Olympic finished 5th in their first season back in the division, losing out in the finals series to Capalaba Bulldogs in the semi-final. In 2013, Olympic FC was awarded a licence to compete in the inaugural National Premier Leagues season, appointing UEFA A Licensed coach Gabor Ganczer as Technical Director.
Olympic was crowned NPL Queensland premiers on August 4, 2013, defeating Moreton Bay United 3–1 to secure in insurmountable lead with two rounds remaining. Following a 2–0 semi-final win over Brisbane Strikers, the club added to its 2013 silverware by defeating Brisbane City 3–3 (3–0) on penalties in the Grand Final at Goodwin Park on September 8, 2013.