The club was founded in 1996 as Al Shabab. It changed its name to Al Muaither in 2004 by decision of the Qatar Olympic Committee. They played exclusively in the Qatari Second Division until 2013. Their first promotion play-off was in the 1999–00 season against Qatar SC. In 2004, Muaither became the first team in history from the second division to win the Sheikh Jassem Cup. They defeated Al Wakrah 2–1 in the final. They finished as runners-up of the Second Division in the 2012 and 2013 season, which earned them promotion play-off matches against Umm Salal and Al Arabi. They lost the first match against Umm Salal, which was the club's second promotion play-off match in its history, by a scoreline of 0–1 after extra time in 2012. They also lost 1–2 against Al Arabi after extra time in 2013. Their president, Saleh Al-Aji, filed a complaint on 23 April against Al Arabi under the pretense that they were fielding a suspended player, Baba Keita. This was according to the leaguestatistics available on the Qatar Football Association's website. The QFA dashed their hope of being promoted by officially stating that the information they presented was not available on the website, and that Muaither must have acquired the information from third-party sources.
It was announced on 7 May 2013 that the Qatar Stars League would expand to 14 clubs, which inferred that Muaither would be promoted to the first division despite losing the relegation play-off. Their first action in the first division was to hire renowned Spanish-French coach, Ladislas Lozano. They were relegated at the end of the 2013–14 season, along with Al Rayyan.
Name
Over history, Muaither's name has been misspelled by local media in numerous forms. In the mid-2000, the club was known as Muaizar, and then in late 2000, the club was known as Al-Mu'aidar. However, the official spelling is Muaither.
