1989年、1st「No More Mr. Nice Guy」でアルバム・デビューを果たす。このアルバムは何と1週間半という短期間で制作された「電子レンジ・アルバム」であったそうだ。後のクラシックとなる"Manifest"は、当時ブルックリンにいたGuruとテキサスの大学寮にいたプレミアの間で電話を通じて作られたらしい。そして、この曲こそが彼らの運命を変えるものとなったのだ。"Manifest"を聴いた映画監督スパイク・リー(ヒップホップ嫌いとして有名であった)は、自分の映画『Mo Better Blues』のシングルをGangstarrに依頼してきたのだ。その曲があの"Jazz Thing"であった。
91年、セカンド・アルバム「Step In The Arena」をリリース。古いジャズやファンクをサンプリングし、今までのヒップホップにない新しいスタイルを打ち出すようになる。この頃、PremierはKRS-OneとRakimから作品プロデュースのオファーがあったというが、自分にまだ自信がなくその話は引き受けなかったという。
94年にリリースした4thアルバム「Hard To Earn」を制作していた時期、GuruとPremierのの仲はかなり険悪であった。しかし、トラブルを抱えながらも"Mass Apeal"といった傑作を収めたこのアルバムは大ヒットを記録する。Premierはこの作品で、サンプリングしたネタをループすることから、チョップ(ネタをバラバラにして加工して使う)する手法を用いるようになり、極端にミニマルなループを作り出すようになった。
その後、各々Jazzmatazzやプロデュース業に忙しくしていたが、98年、5作目となる「Moment Of Truth」をリリースする。Chrysalisの閉鎖からVirgin傘下のNoo Trybeへ移籍しリリースしたこの作品では、解散という危機を乗り越え、お互いを唯一無二の個性を持つDJ/MC、そしてアーティストとしてリスペクトし合い完成させた傑作として高い評価を得た。
そしてオリジナル・アルバムとしては実に5年ぶりとなるニューアルバム「Ownerz」を6月にリリース。アルバムからのリード・シングル"Skills / Natura"は先にプロモ盤が出回り、プリモのタイトな音作りと、時代に流されず自分達のスタイルを独自に進化させたそのサウンドに渋谷近辺ではかなり話題となった。新作には、Boy Bigをフィーチャーしたフックが印象的なセカンド・シングル"Nice Girl,Wrong Place "を始め、Snoop Doggが参加した和風トラックの"In This Time"など話題の楽曲もいくらか収録しつつ、全体的にアンダーグラウンドの薫り漂うクール、かつエモーショナルな作品に仕上がった。