Vienas talentingiausių Niujorko underground'o reperių Cormega išgarsėjo dar ir dėl bendradarbiavimo su Nas. Abi Queensbridge'o žvaigždės turėjo vienodą potencialą išplaukti į platesnius vandenis, tačiau pradžioje tik Nas tapo nacionaline garsenybe, tuo tarpu Cormega ilgą laiką turėjo tenkintis underground'o klausytojų pripažinimu. Kol Nas vieną po kito leido neprilygstamus albumus, Cormega dominavo Niujorko miksteipų scenoje ir tik 2001-aisiais įrašė debiutinį albumą. Tai įvyko praėjus penkiems metams nuo Cormega pasirodymo Nas albumo "It Was Written..." (1996 m.) kūrinyje "Affirmative Action". Būtent po to pasirodymo Cormega ir tapo Hip-Hop'o didžėjų numylėtiniu, be to jo gangsterišką įvaizdį pamėgo daugelis repo gerbėjų. Cormega dažniausiai repavo apie tragiškąją gyvenimo gatvėje pusę, tačiau jis tai darė su nepaprastu įžvalgumu, pasitelkdamas į pagalbą aiškų žodžių tarimą ir patrauklų balso tembrą. Kai pagaliau 2001-aisiais pasirodė debiutinis reperio albumas "The Realness", kritikai ir klausytojai buvo priversti skirti pačius aukščiausius balus.

Nas ir Cormega, Queensbridge'o atstovai, tapo draugais praėjusio dešimtmečio pradžioje ir nuo to laiko kartu įrašinėjo. Deja Cormega padarė nusikaltimą ir sėdo į kalėjimą, tuo tarpu Nas pradėjo dirbti prie debiutinio albumo "Illmatic" (1994 m.), kuris išgarsino reperį visame pasaulyje. Nas nepamiršo kalėjime sėdinčio draugo ir vieną albumo kūrinį, pavadinimu "One Love", skyrė Cormega'i, kuris išėjo į laisvę netrukus po to. Sekantis Nas albumas "It Was Written" pasirodė 1996-aisiais ir tie metai tapo Cormega atspirties tašku, nuo kurio jis pradėjo savo karjerą. Kartu su Nas, AZ, ir Foxy Brown įrašytas kūrinys "Affirmative Action" buvo puikus pagrindas ateities planams, kuriuos iš dalies sužlugdė pats Nas. Jis norėjo sukurti grupę The Firm (AZ, Foxy Brown, Nas, Nature) be Cormega, kurį pakeitė kitas Queens'o reperis Nature. Ketvertas įrašinėjo albumą, o Cormega tuo metu liko visiškame šešėlyje ir iš pykčio įrašė dis'ą "Fuck Nas and Nature", kurį išplatino gatvėse kartu su kitais įrašais.

Kai draugystė tarp Nas ir Cormega nutrūko, pastarasis pradėjo ieškotis būdų tęsti solo karjerą. Kadangi reperių konfliktai tuo metu jau domino norinčias iš to pasipelnyti įrašų kompanijas, nieko nenustebino, kad prestižinis leiblas "Def Jam Records" pasiūlė kontraktą Cormega'i. Deja tai nebuvo ta kompanija, kuri galėjo rimtai užsiimti debiutinio albumo išleidimu. Cormega išleido dvigubą singlą "Angel Dust"/"Killaz Theme II" ir įrašė visą albumą "The Testament", kuris dėl kažkokių priežasčių niekada nesulaukė kompanijos vadovų dėmesio ir neišvydo dienos šviesos. Galbūt tai buvo mažėjančios įtampos tarp Nas ir Cormega pasekmė, bet viena aišku - įrašų kompanija, kuriai atlikėjas įdomus tik tol, kol gali nešti pelną, ne vieta talentingam reperiui. Cormega judėjo toliau ir tapo nepriklausomu atlikėju, vėl grįždamas į gatves. Jis įkūrė nuosavą leiblą "Legal Hustle" ir, sudaręs leidybos sutartį su "Landspeed Records", pradėjo įrašinėti debiutinį albumą "The Realness", kurio piratinės versijos pasirodė internete dar daug anksčiau nei legaliosios. Albumas buvo išleistas 2001-aisiais ir tapo vienu geriausių metų repo įrašų - bent jau taip jį pakrikštijo klausytojai. "The Realness" buvo tas albumas, kuris parodė tikruosius Cormega sugebėjimus ir surinko nemenką gerbėjų būrį. Jie pamėgo Queens'o reperį už gyvybingą artikuliaciją ir aistringą gatvės kūrybą. Svarbiausia, kad Cormega buvo visapusiškai talentingas ir visapusiškai nepriklausomas.

Kai pagaliau Cormega gavo pelnytą pripažinimą, garsas apie jį pasiekė ir Nas ausį. Šis tuo metu įrašinėjo albumą "Stillmatic" (2001 m.) ir, daugelio nuostabai, įtraukė į jo turinį dis'ą Cormega'i. "Destroy & Rebuild" buvo tarsi pavėluotas atsakas į "Fuck Nas and Nature". Cormega į tai sureagavo žaibiškai ir tuoj pat įrašė antrą dis'ą "The Slick Response", o vėliau - "Love in Love Out". Pastarasis dis'as buvo įtrauktas į antrą Cormega albumą "The True Meaning" (2002 m.). Prieš pastorojo disko pasirodymą "Body Shop Records" išleido gatvinių Cormega įrašų, surinktų iš įvairių miksteipų, rinkinį "Hustler/Rapper", kuriame buvo tokie underground'iniai hitai kaip "Angel Dust" ir "Realmatic" - dar vienas dis'as Nas'ui. Nors 2002-ųjų vasarą išleistas albumas "The True Meaning" nebuvo įrašinėjamas vienoje didžiųjų kompanijų, prie jo kūrimo prisidėjo garsūs prodiuseriai Large Professor ir the Alchemist. Šis albumas buvo pirmasis Cormega darbas, kuriam pavyko pakilti į "Billboard'o" chart'o Top 100. Trečiasis reperio albumas "Legal Hustle" pasirodė 2004-ųjų pavasarį ir buvo dar sėkmingesnis. Jame beveik nebuvo solo įrašų, vietoje to daugybė bendrų projektų su M.O.P., Kurupt, Ghostface ir Large Professor.