Our Lady Peaceが結成されたのは1992年、マイク（ギター）がトロントの『Now』というフリーペーパーに出したバンドメンバー募集の広告に、当時大学生だったレイン（ヴォーカル）が応えたことがきっかけでした。ちなみに、結成後しばらくはドラマーとベーシストは今とは全く違う人だったらしく、その時のラインナップで撮られたらしい、「Out of Here」という曲のビデオクリップがあります。
結成から１年ほど経った段階で、彼らは3曲入りのデモテープを作り、いくつかのレーベルにアプローチします。その結果、ソニー、ゲフィン、インタースコープといったレーベルから反応があり、中でも最も活動上の自由を約束してくれたソニーと契約することになりました。この時、OLPはまだ10数回しかライブをしたことがなく、インディーでの下積み経験もありませんでした（本当にラッキーなスタートですよね(^_^)）。この頃、オーディションによってジェレミー（ドラム）とクリス（ベース）がバンドに加入しました。
1995年には、ファーストアルバムである『Naveed』がリリースされました。このアルバムを引っさげ、OLPは500回以上という途方もない数のライブをこなすことになります。しかしその結果、彼らは着実に注目を集める存在となり、アラニス・モリセットや、ラジオでシングルの「Starseed」を耳にしたロバート・プラントからは、「ぜひ自分のコンサートのオープニングアクトをやってほしい」と個人的に頼まれるほどになりました。しかし、ベースのクリスが、「音楽的にも人間的にも、目指す方向が他のメンバーとずれてきてしまった」という理由で脱退。代わりに、以前からレインとは友達だった現在のベーシスト、ダンカンが加わります。
1997年には、セカンドアルバム『Clumsy』をリリース。結果的にこのアルバムはカナダ、アメリカ、およびその他の国でトータル250万枚以上売れる大ヒットとなり、彼らは名実共にカナダを代表するバンドとなりました。このアルバムからのシングル「Clumsy」はアメリカでもヒットし、ビルボードのモダンロックチャートの（確か）5位ぐらいまで上がりました。
この後、ウッドストック出演を経て、1999年にはサードアルバム『Happiness．．．is not a fish that you can catch』（邦題『ハピネス』）がリリースされました。このアルバムは、OLPのアルバムとしては初めて日本盤化されたものです（『Naveed』も『Clumsy』も、残念ながら国内盤は出ていません）。イギリスでも、OLPはこのアルバムを機に本格的に注目され始めたらしく、着実にインターナショナルなバンドとしての第一歩を踏み出しました。
そして2000年の12月には、前作からわずか1年余りという期間を経て、4枚目となるアルバム『Spiritual Machines』をカナダでリリースしました（ちなみに、アメリカや日本では2001年に発売されました）。なお、このアルバムではブレンダン・オブライエン（パール・ジャムなどを手掛けたプロデューサー）がミックスを担当しており、マット・キャメロン（元サウンドガーデン／現パール・ジャムのドラマー）がゲスト参加しています。このアルバムは批評家達にも高く評価され、その年のJuno賞（カナダ版グラミー賞です）ではOLPが全アーティスト中最多のノミネーションを獲得しました。
2002年には、5枚目となるアルバム『Gravity』をリリース。このアルバムは、それまでのアルバムでずっと一緒に仕事をしてきたプロデューサー、アーノルド・ラニ（OLPの他には、Simple Planなどを手掛けています）の元を離れ、ボブ・ロック（メタリカなどとの仕事で有名です）と組んだ初めてのアルバムで、商業的にも大きな成功を収めました（このアルバムからの先行シングル「Somewhere Out There」がモダンロック系のラジオ局だけにとどまらず、ヒットチャート系のラジオ局でもエアプレイをかせぐヒットとなったおかげで、『Gravity』はBillboardのアルバムチャートで初登場9位を記録しました）。しかし、このアルバムのレコーディング中に、ギタリストのマイクが音楽性の違いを理由に脱退。その後任として、デトロイト出身のスティーヴが新たにバンドに加わりました。スティーヴは名門音大、Berklee College of Musicの卒業生で、OLPに加入する前には、エンジニアとして色々な有名ミュージシャンのアルバム制作に携わっていたこともあるようです。
2003年には初となるライブアルバム&ライブDVDをリリースしたOLP。また、2004年にはアヴリル・ラヴィーンのセカンドアルバム『Under My Skin』にレインがプロデューサーとして参加するなど、活動の幅を広げました（ちなみに、レインがアヴリルのアルバムに参加することになったのは、レインの奥様であるカナダの人気女性アーティスト、シャンタール・クレヴィアジックのアイディアだったようです。シャンタールとアヴリルは元々親友で、このアルバムのために一緒に曲作りをしていたのですが、ある日シャンタールが「レインにプロデュースをやらせてみない？」と提案し、アヴリルもそれはいいアイディアだと思ったため、レインの参加が実現したそう。なお、レインはプロデュースの他にも、「Fall To Pieces」という曲ではアヴリルと共作もしています）。再びボブ・ロックと組んだ6作目となるニューアルバムも、2005年春頃の発売が予定されています。