Jednostce tej planowano nadać nazwę „Nieustraszimyj”, od której wzięło się zachodnie określenie całego typoszeregu. Warto zaznaczyć, że próbowano przeforsować inną nazwę, „Nowik”, ta jednak nie znalazła uznania. Wodowanie jednostki miało miejsce w maju 1988 roku, a oficjalne wcielenie do służby odbyło się w grudniu 1990 roku. Trzy miesiące później fregatę przydzielono do Floty Bałtyckiej.
Podczas gdy konstrukcja jednostki „Nieustraszimyj” przebiegała bez zakłóceń, budowa kolejnych okrętów napotkała ogromne trudności finansowe, spowodowane upadkiem Związku Radzieckiego. Stępkę pod drugą fregatę o nazwie „Niepristupnyj” (w sierpniu 1995 roku nazwę zmieniono na „Jarosław Mudryj”) położono w maju 1988 roku, zaraz po wodowaniu pierwszej jednostki. Kadłub drugiego okrętu typoszeregu Nieustraszimyj spłynął na wodę w 1990 roku, a według niektórych źródeł w maju 1991 roku. Właśnie wtedy zaczęły się problemy finansowe, z powodu których budowę wstrzymano aż do 2002 roku. W chwili podjęcia decyzji o rozpoczęciu prac fregata ukończona była w 75 procentach. W 2003 roku stopień wykończenia osiągnął pułap 79 procent. Na początku 2004 roku planowano, że jednostka znajdzie się w szeregach floty w 2005 roku, jednak ponownie napotkano problemy finansowe. Decyzja o ponownym wznowieniu prac wykończeniowych zapadła w 2007 roku, gdy jednostka była gotowa w ponad 80 procentach. W końcu fregata wypłynęła na pierwsze próby morskie w grudniu 2008 roku i wydawało się, że nie będzie już dalszych problemów. okazało się inaczej w maju 2009 roku, gdy na pokładzie rozbił się lądujący śmigłowiec Kamow Ka-27PŁ (NATO: Helix-A), uszkadzając konstrukcję kadłuba i jeden z modułów systemu obrony bezpośredniej model 3R-87E Kortik (Kashtan / CADS-N-1). Spowodowało to niewielkie opóźnienie w przekazaniu okrętu marynarce wojennej. Ostatecznie fregata „Jaroslaw Mudryj” znalazła się w służbie w lipcu 2009 roku i podobnie jak jednostka „Nieustraszimyj” przydzielona została do Floty Bałtyckiej z bazą w Bałtijsku.
W 1993 roku w stoczni Jantar w Kaliningradzie rozpoczęła się budowa trzeciego okrętu, dla którego planowano nazwę „Tuman”. Prace wstrzymano jednak wkrótce po rozpoczęciu z powodu braku funduszy. W 1996 roku jednostka była ukończona w 30 procentach. W listopadzie 1998 roku nieukończony kadłub zwodowano, gdyż blokował suchy dok, potrzebny do rozpoczęcia remontu norweskiego statku handlowego. Kontrakt na jego naprawę był zdecydowanie bardziej opłacalny niż trzymanie okrętu, którego finansowanie wstrzymano i nie było perspektyw na ich wznowienie. Zaraz po wodowaniu podjęto decyzję o sprzedaży kadłuba na złom, by chociaż w części zwróciły się poniesione przez stocznię koszty inwestycji w infrastrukturę do budowania fregat projektu 1154.0 Jastrieb.
Być może nie tylko kwestie finansowe miały wpływ na powolne budowanie jednostek i skończenie serii jedynie na dwóch okrętach. Już od samego początku projekt 1154.0 Jastrieb miał sporo przeciwników wśród przedstawicieli przemysłu okrętowego i marynarki wojennej. Zagadką pozostaje fakt, dlaczego w trudnym okresie po upadku Związku Radzieckiego, kiedy fundusze były bardzo skromne, budowa tych jednostek była wstrzymana, a pieniądze pompowano w zupełnie inne, istniejące w fazie koncepcyjnej projekty. Taki stan rzeczy był zapewne wynikiem lobbingu na niekorzyść floty, a z pożytkiem dla przemysłu, dla którego budowa większych jednostek była znacznie bardziej opłacalna i stwarzała większe struktury organizacyjne, pozwalając na obsadzanie większej ilości lukratywnych stanowisk.
Przebieg służby jednostek projektu 1154.0 jak dotychczas nie obfitował w szczególne wydarzenia. Spory wpływ na to miał fakt, że po upadku Związku Radzieckiego flota była chronicznie niedofinansowana, przez co nie miała środków na prowadzenie regularnych operacji. Dopiero w połowie pierwszej dekady XXI wieku rosyjskie okręty zaczęły odważniej wychodzić na wody oceaniczne, o czym może świadczyć wizyta niszczyciela „Admiral Czabanienko” (NATO: typ Udaloy II) w Wenezueli pod koniec 2008 roku.
W 2004, 2006, 2007 i 2008 roku „Nieustraszimyj” brał udział w międzynarodowych ćwiczeniach na Bałtyku – Baltops. We wrześniu 2008 roku fregatę wysłano na wody okalające Półwysep Somalijski w celu zwalczania aktów pirackich. Okręt miał dołączyć do sił międzynarodowych, a pierwszym zadaniem było przechwycenie porwanego przez piratów ukraińskiego statku „Faina”, transportującego do Kenii czołgi i amunicję. Wraz z jednostkami amerykańskimi „Nieustraszimyj” okrążył porwany statek i zmusił piratów do poddania się. W pierwszej połowie listopada 2008 roku śmigłowiec z pokładu rosyjskiej jednostki, wraz z maszyną z HMS „Cumberland” (F 85) typu Broadsword uczestniczył w akcji udaremniającej porwanie przez piratów duńskiego statku „Powerful”. Oficjalne stanowisko marynarki wojennej Wielkiej Brytanii kwestionuje jednak faktyczne uczestnictwo rosyjskiego śmigłowca, gdyż to komandosi z maszyny brytyjskiej zapobiegli porwaniu. Na początku stycznia 2009 roku „Nieustraszimyj” został zastąpiony na wodach Zatoki Adeńskiej przez niszczyciel „Admirał Winogradow”. Fregata powróciła do bazy w Bałtijsku na Morzu Bałtyckim w pierwszych dniach lutego 2009 roku.
W konstrukcji jednostek projektu 1154.0 Jastrieb widać nie tylko rozwiązania typowe rosyjskie, ale i wpływy zachodniej myśli. Stalowy kadłub otrzymał kształt charakterystyczny dla innych okrętów radzieckiej floty. Mniej więcej od śródokręcia wznosi się ku górze, a nowością jest wypłaszczenie na samym przodzie, pozwalające na prowadzenie ognia na wprost z dziobowej armaty przy zerowym kącie podniesienia lufy. Kadłub cechuje się wysoką wolną burtą, która zapewniała dobrą dzielność morską.
