Die Band wurde vom Leadsänger Kevin Barnes gegründet und benannt nach einer gescheiterten Romanze mit einer Frau aus Montreal. Barnes war das einzige Mitglied der "Gruppe" vor seinem Umzug nach Athens, Georgia. Dort traf er auf Derek Almstead, der später Mitglied von Circulatory System, M Coast, Elf Power, u.a. wurde und Bryan Poole, der auch unter dem Namen The Late B.P. Helium auftritt. Zusammen haben sie ihr erstes Album, Cherry Peel aufgenommen, sowie die EP The Bird Who Continues to Eat the Rabbit's Flower und das zweite Album, The Bedside Drama: A Petite Tragedy.

Nachdem die Produktion für ihr drittes Album, The Gay Parade, 1998 begann, verließ Poole die Band, um sich auf seine Pflichten bei Elf Power, einer anderen Band aus dem Elephant Six Kollektiv zu konzentrieren. Barnes warb Jamey Huggins und Dottie Alexander an, in der Band verschiedene Instrumente zu spielen und Derek stieg von Schlagzeug auf den Bass um. Kurz darauf stieß auch Andy Gonzales von Marshmallow Coast zur Band.

Die Band veröffentlichte eine Reihe von Singles und ein Re-Release von The Bird Who Continues to Eat the Rabbit's Flower vor ihrem dritten Album The Gay Parade im Jahre 1999. Nach der Veröffentlichung von The Gay Parade unterschrieb die Band bei Kindercore Records. 2001 folgte dann mit Coquelicot Asleep in the Poppies: A Variety of Whimsical Verse das vierte Album.

Das fünfte Album, Aldhils Arboretum in Jahre 2002 war etwas anders als seine Vorgänger und wies struktuiertere Songs auf. Dieses Album stellt einen Wendepunkt in der Musik von of Montreal dar, hin zu einfacher zu tanzenden Rhythmen. Hieran schloss sich eine erfolgreiche Tour an, inklusive of Montreals erste Auftritt im Vereinigten Königreich.

Kindercore Records ist kurz danach geschlossen worden und die Zukunft von of Montreal war bedroht. Kevin Barnes heiratete und Andy und Derek verließen die Band. Barnes schrieb und spielte das meiste auf ihrem Album Satanic Panic in the Attic alleine ein. 2004 bei Polyvinyl Records erschienen, wurde es bis dahin eines ihrer erfolgreichsten Alben. Für die Tour stieß Bryan Poole wieder zur Band und Kevins Frau Nina spielte am Bass.

Dieser Stil blieb bei ihrem 2005er Album The Sunlandic Twins bestehen, welches fast noch mehr eine Solo-Leistung von Barnes war. 2006 erschienen mehrere Sammlungen von Singles.

Barnes nahm den Großteil des 2007er Albums Hissing Fauna, Are You the Destroyer? selbst auf, als er in Norwegen und Athens lebte. Die Hinwendung zu autobiographischen Themen wie Suizid, Depression und Isolation auf dem Album sind ein direktes Produkt seines aufgewühlten Lebens in dieser Zeit. Zu diesem Album erschien auch eine Begleit-EP, Icons, Abstract Thee.

Die Band hat einen Stil der typisch ist für viele der Elephant 6 Bands aufgrund ihres Interesse, musikalische Experimente und die Grundlagen der Pop-Musik wie eingängige Melodien und mitzusingende Refrains zu kombinieren.

Ihr Stil ist bekannt dafür, zwischen Alben zu wechseln. Am Anfang verfolgte die Band einen simple, lo-fi Indie Pop Sound, mit Angrenzungen an Twee Pop. Mit der Zeit ging die Band über zu vollerem Sound, wie auf den Konzept-Alben The Gay Parade, und dessen Nachfolger, Coquelicot Asleep in the Poppies: A Variety of Whimsical Verse Diese Alben beinhalteten erzählerische Texte, anders als die persönlichen Texte ihrer Vorgänger.

Das Album Satanic Panic in the Attic markierte das Ergebnis eines gewachsenen Wechsels des Stils. Die Musik veränderte sich zu einer mehr elektronischeren, mit traditionellen Strukturen, was auf den folgenden Alben beibehalten wurde.

Lyrisch gesehen wandelte sich der Stil dramatisch in den Jahren. Am Anfang waren die meisten Lieder Erzählungen persönlicher oder witziger Situationen. Dies änderte sich mit The Gay Parade, wo die meisten Lieder kurze Geschichten beinhalteten, die sich um fiktive Charaktere drehten. Aldhil's Arboretum markierte eine leichte Rückkehr zu vorherigen Texten, jedoch mit auflockernden, klassischen Elementen wie Refrains, die auf den beiden Alben davor fehlten. Dieser Stil blieb bei den folgenden Alben erhalten, während das bislang letzte Album Hissing Fauna: Are You the Destroyer? viel persönlichere Texte verwendet, deren Zeilen die Emotionen des Sängers wiedergeben.

Eine andere, einmalige Qualität der Band ist es, offensichtlich schaurige oder traurige Texte mit fröhlichen Melodien zu verbinden, so dass Lieder wie "Old People in the Cemetery", die von Apathie, Einsamkeit und Tod handeln, mit fröhlichen Musik kontrastiert werden.