Początki kariery, pierwsze płyty

Zespół został założony w 1997 roku przez czterech wokalistów: Wiaczesława Bodolikę, Pitera Dżejsona, Żana Grigorjewa-Milimierowa i Dmitrija Łanskoja. Dwa lata później wydali oni swój pierwszy album studyjny, zatytułowany Griaznyje tancy (ros. Грязные танцы). W 2000 roku ukazał się ich singiel „Wostocznaja piesnia”, który zapowiadał drugą płytę zespołu, Pochod na Wostok (ros. Поход На Восток), wydaną w kolejnym roku. Niedługo potem formacja opublikowała album pt. Wsie wkluczeno (ros. Все включено). W listopadzie tego samego roku ze składu formacji odszedł Łanskoj, który został zastąpiony przez Marata Czanyszewa.

2002: Konkurs Piosenki Eurowizji, Diewoczka s siewiera, Piatyj okiean

W marcu 2002 roku zespół został wybrany wewnętrznie przez krajową stację Pierwyj kanał na reprezentantów Rosji podczas 47. Konkursu Piosenki Eurowizji. Ich konkursowa propozycja, „Northern Girl”, została wyselekcjonowana spośród 11 742 kandydatur. Na czas konkursu zespół zmienił swoją nazwę na Prime Minister, aby nadać jej międzynarodowe brzmienie. W maju formacja wystąpiła w finale konkursu, w którym zajęła ostatecznie 10. miejsce, zdobywając łącznie 55 punktów. Po finale konkursu wokaliści wydali oświadczenie, w którym podziękowali nadawcy za możliwość udziału, a swój wynik tłumaczyli wysokim napięciem, zmęczeniem oraz wypalaniem części zespołu. Swój występ uznali natomiast za szczyt góry lodowej z powodu dużej ilości wywiadów z mediami oraz męczących prób do prezentacji w finale.

W tym samym roku zespół wydał swój kolejny album studyjny, zatytułowany Diewoczka s siewiera (ros. Девочка с севера), który promował m.in. eurowizyjny utwór „Northern Girl” oraz jego rosyjskojęzyczna, tytułowa wersja. Niedługo po premierze, utwór trafił na pierwsze miejsce krajowych list przebojów. Rok później na rynku ukazała się płyta pt. Piatyj okiean (ros. Пятый океан).

2004-05: Rozpad, nowy skład

W 2004 roku zespół wydał swój debiutancki album kompilacyjny, zatytułowany Zołotaja sierija (ros. Золотая серия), na której znalazły się największe przeboje grupy, w tym m.in. utwory „Northern Girl” i „Wostocznaja piesnia”. W tym samym roku premierę miał debiutancki album koncertowy grupy, pt. Osobo ważnyje piersony.

W związku z nieporozumieniami z producentem zespołu, Grigorjewem-Milimierowem, z projektu odeszli Czanyszew i Bodolika, którzy zaczęli działać samodzielnie pod nazwą Grupa PM. Wówczas dawny producent formacji, Eugene Friedland, ustanowił nowy skład grupy: Taras Diemczuk, Siergiej Diemianczuk, Anton Naumow, Wasilij Kiriejew i Amarchuu Borchuu. W tym samym czasie ukazała się kolejna płyta koncertowa zespołu, Priemjer-ministr w Rossii. №1 (ros. Премьер-министр в России. №1; CD/DVD), a także składanka MP3 kollekcyja (ros. MP3 коллекция).

Od 2006: 8 marta i My tak chotieli

W 2006 roku formacja w nowym składzie wydała specjalny album studyjny zatytułowany 8 marta (ros. 8 Марта), który został nagrany z okazji Dnia Matki. W 2008 roku ukazał się ich kolejny krążek pt. My tak chotieli (ros. Мы так хотели). Płyta promowana była m.in. przez singiel, z którym zespół wziął udział w krajowych eliminacjach eurowizyjnych. 9 marca muzycy wystąpili w finale selekcji i zajęli ostatecznie dziewiąte miejsce.