Their nickname comes from the fact that in their first two seasons they won two trophies (Campeonato Nacional da 3ª Divisão and Campeonato Nacional da 2ª Divisão). In 2009-10 they win their most important title, the Taça de Portugal de Futsal for the first time, beating Benfica in the final. Benfica scored first, but Diego Sol equalized in the second half, Marcelinho in the final seconds of Extra time scored the decisive goal. Notable players included Marcão, Diego Sol, Pedro Cary, Paulinho and Marcelinho.
More recently, Belenenes encountered some financial problems, including a request for Insolvency after unpaid salaries to former futsal player Formiga and a pledge of the clubs trophies for unpaid construction work done to Estádio do Restelo. Belenenses was relegated in 2011/2012 after a play-out.