2007-ci il martın 3-də tarixində ilk rəsmi matçın onilliyini qeyd edən komanda dağılmış paytaxt klubu "Semetey"in oyunçularından qurulmuşdu.^{[mənbə göstərin]} Biznesmen Askar Salımbekovun təsis etdiyi klub birinci dəstədə "Alqa-SKA"nı 1:0 yenməklə debüt etdi. İkinci cəhddən elita arzusu gerçəkləşən Narın təmsilçisi 1999-cu ildə güclülər sırasında debütünü 5-ci yerdə bitirdi. Əslən Narın şəhərindən olan ölkə çempionatları tarixinin ən yaxşı qolçusu Zamirbek Jumaqulovun 2000-ci ildə komandaya gəlişi heç nəyi dəyişmədi – 6-cı yer. Qolçular sırasında üçüncü olan forvard növbəti mövsüm həm özü bu pillədə qaldı, həm də "Dordoy" ilk mükafatına – "bürünc"ə qovuşdu. 2002 və 2003-cü illərdə Mixail Tyaqusovun rəhbərliyi altında daha iki bürünc qazanıldı. Hər iki mövsümdə ikinci qolçu olan Zamirbek isə 2002-nin ən yaxşı futbolçusu da seçildi. İldən-ilə heyəti güclənən komanda həm də irəli addımlayırdı.

2004-cü il əlamətdar hadisələrlə başladı. Hələ SSRİ dönəmində Əlcəzairdə çalışdırdığı klubu çempion edən Boris Podkorıtov komandaya dəvət olundu. Təbii ki, Moskva "Lokomotiv"inin 1948 təvəllüdlü sabiq oyunçusu heyətə də əl gəzdirdi. Elə komandanın ilk dəfə "Dordoy" yox, "Dordoy-Dinamo" kimi çıxış etdiyini də xatırladaq. Ən yaxın izləyicisini 5 xal qabaqlayan Podkorıtovun yetirmələri bir həftə əvvəl qazandığı ölkə kubokunu ilk çempionluqla tamamladı. Üstəlik, mövsümün ən yaxşılarının hamısı – qapıçı, müdafiəçi, hücumçu, bombardir, məşqçi Narın təmsilçisinin üzvləri idi.

İkinci "dubl" daha çətin başa gəldi. "Birlik kuboku"nda "Kaunas" və "Paxtakor"a minimal fərqlə yenilən qırğızlar gürcülərlə əzmkar heç-heçəyə sevindi. Böyükhesablı məğlubiyyətlərə adət edən həmyerlilərindən fərqlənən narınlılar ardından Podkorıtovu itirdi. Yetirmələrindən birini də götürüb Qazaxıstan "Jetısu"suna gedən mütəxəssis bir də son tur ərəfəsində peyda oldu. O vaxta qədər isə AFK prezidentinin kubokunda finalda yenilən "Dordoy-Dinamo" ölkə kubokunu qazanmışdı, çempionluğun biraddımlığındaydı. "Şoro-SKA"yla heç-heçənin gətirəcəyi çempionluq yubandı. Yenilgi hər şeyi "qızıl oyun"a saxladı. Narınlılar "Şoro-SKA"nı penalti seriyasında yenib ardıbıl ikinci "dubl"a imza atdı. 2006-cı ildə də heç nə dəyişmədi: Podkorıtov və yetirmələri Moskvada qrup sonuncusu olub, qitə kubokunun finalına çıxdı. Fərq onda oldu ki, "Birlik kuboku"nda üç yenilgi alındı, AFK prezidentinin kuboku isə Narına gətirildi. Daxili yarışlarda yenə – ardıcıl ikinci "qızıl oyun" və yenə – ardıcıl üçüncü "qızıl dubl" qeydə alındı.^{[mənbə göstərin]}