The club was founded in 1957 as Hollandia Soccer Club by Dutch immigrants. From the start they were based at grounds in the Brisbane suburb of Darra and then moved to Pine Road Richlands, where they still play. In the early 1970s, all clubs were required to abandon 'ethnic' names and they then adopted the name Brisbane Lions.
In 1977 the Lions were invited to play in the National Soccer League and played in the league as Brisbane Lions until the end of the 1988 season. Former Manchester United and Northern Ireland legend George Best made four appearances for the team during the 1983/84 season. From 1989 the Brisbane Lions played in the Brisbane Premier League. After coming to an agreement with the newly formed Brisbane Lions AFL club, they changed their name to the current Queensland Lions.
In 2004 it was announced that the Lions had won the right to compete in the A-League. Operating as Queensland Roar the club was once again represented in an Australian national league. Subsequent changes to the ownership structure of the Roar allowed the Queensland Lions to re-enter the Brisbane competition in Premier Division 1, where they will continue to play in 2011 after finishing 9th in 2010.
The Queensland Lions operate a licensed club with a membership of over 16,000, with 176 gaming machines.
The club has three senior and three junior teams competing in the Brisbane Women's Soccer League. The Lions had 38 junior teams competing in BSDJSA competition in 2005.