Formed by a group of friends in Sorel-Tracy, Québec, the band made itself known in 2004 with the release of its first album, Le Compte complet. Critics welcomed the disc with positive reviews, which allowed the group to become instantly famous in the Quebec music scene. Several of its songs, such as "Le Métronome" and "La Valérie", were prominent mainstays on several Quebec radio stations. For the production of the album, the group turned to Martin Pelland from fellow Montreal band The Dears.
In the months that followed the release of their first album, Malajube launched a tour across Quebec, participating in several major festivals, such as Les FrancoFolies de Montréal.
In February 2006, the quartet released its second album, Trompe-l'œil, which also received a warm welcome on the part of Quebec media. Collaborations with singer Pierre Lapointe, Québécois rap group Loco Locass and Valerie Jodoin Keaton (The Dears), and the use of a wide variety of instruments has contributed to the album's success in addition to audio engineer/record producer Ryan Battistuzzi's (We Are Wolves, Death from Above 1979, Blessed by a Broken Heart) production work. Trompe-l'œil also began to attract attention in English Canada in July, when it was shortlisted for the 2006 Polaris Music Prize, and in the United States in October, when it was a featured review on Pitchfork Media. In 2006, they won three Félix Awards at the 28th edition of the Gala de l'ADISQ: two for Trompe-l'œil, "Best alternative album" and "Best cover art" while they were proclaimed "Revelation of the year 2006". The Canadian Broadcasting Corporation has described them as one of very few Quebec musical groups who have achieved success in English Canada despite not performing in English, something the band states they have no interest in doing.
On October 17, 2006, Malajube released their CD Trompe-l'œil in the U.S. They also participated in the CMJ Music Marathon in New York City on November 2, 2006. In 2007 they did tour the USA, opening for Snowden, passing through Austin's South by Southwest festival.
On May 4, 2007, Trompe-l'œil was released in Europe and in Japan on the German label City Slang. A Take-Away Show acoustic video session shot by Vincent Moon.
The band's song "Montreal -40°C" was featured in a Rogers Wireless commercial, and another song, "Ton plat favori", was in a Zellers commercial. "Pâte filo" was also featured in a commercial for Radio Shack in the United States. Regarding the French lyrics, Augustin said in an interview: "I am sure the language, even if we say 'yeah., people from the states are interested in French music We are exportable,' which is something I hear a lot, it would still be difficult to understand that. We have a chance with Malajube, because people get the music. Even if it is in French and people don't get the lyrics, the music does the work. It talks to people." When asked if Malajube find it odd to play a show to an English-speaking crowd and have people singing along who have no idea what they’re singing, Cournoyer said: "Yes, it’s very funny. But wherever we go, there always seems to be a couple of Quebecers in the crowd, who teach other people."
In spring of 2009, with the release of Labyrinthes, Malajube was featured as the X3 Artist of the month by Aux.tv, CBC Radio 3 and Exclaim! for March 2009. They also toured the US again passing by the Festival International de Louisiane. in Lafayette and were once again shortlisted for the 2009 Polaris Music Prize. They also returned to New York in the fall for the CMJ Music Marathon.
Malajube composed and performed the soundtrack for the 2010 Canadian film The Trotsky starring Jay Baruchel and Colm Feore.
In 2010 Malajube went to Vancouver to perform at the 2010 Winter Olympics.
In February 2010, the National Film Board of Canada's French Program produced an interactive video for the unreleased song "Contrôle", called "100 mots pour la folie". The interactive experience is an invitation to explore our perceptions of mental illness through a visit of NFB archives extracts linked to words associated to mental illness and insanity the users type in to build their own music video of the band piece.
In January 2011, Malajube was nominated for The 10th Annual Independent Music Awards in the EP category for Contrôle.
On January 20, 2011, the band released an official announcement that their fourth album, La Caverne, would be released on April 19. A track from the album, "Synesthésie", was released on the band's website on February 12, 2011.
The band is currently on hiatus. Francis Mineau released an album by his side project Oothèque in 2013, and Julien Mineau's side project Fontarabie released an album in 2014.Julien Mineau (lyrics, vocals, and guitar)
Francis Mineau (drums)
Mathieu Cournoyer (bass)
Thomas Augustin (keyboards, vocals)
Rémi Nadeau-Aubin (guitar, 2002–2003)
Renaud Bastien (guitar/keyboards, 2006–2007)
Le Compte complet, (2004)
Étienne d'août single (2007)
Contrôle EP, (2009)
Synesthésie (Single 7" vinyl) (2011)
La caverne, (2011)
Oeil pour oeil (Single from the film Good Neighbours), (2012)