Már régóta senki nem vitatja, hogy Missy "Misdemeanour" Elliott és producere, Tim Mosley (művésznevén Timbaland) a hiphop és az R&B világának legsikeresebb és szakmailag is elismert kettősét alkotják. Ez a partnerség nemcsak sikeres albumokban vagy világslágerekben mutatkozott meg, hanem - főként Missy karrierjének kezdeti szakaszában - abban a hatásban is, amit a kettős az egész műfajra gyakorolt. Ezért is jelentett meglepetést, hogy új lemezén Missy csak két számban működik együtt Timbalanddal.
Az már kevésbé meglepő, hogy a The Cookbook névre keresztelt új lemez nélküle is megáll a saját lábán, sőt, a mérsékelt sikerű This Is Not A Test! című előző albumhoz képest valós előrelépést is jelent. Missy Elliott ugyanis nem véletlenül lett minden idők legsikeresebb női rappere, aki ráadásul egy sereg másik előadó karrierjét is egyengette már a múltban. Az is igaz azonban, hogy az utóbbi időben már inkább az utóbbi (tehát a sikeres világsztár) szerepet töltötte be a műfaj megújítója helyett, így aztán ideje volt, hogy ismét valami újat próbáljon ki.
Missy eddigi karrierje ugyanis eddig sem szűkölködött az újdonságok keresésében és a változatosságban. A virginiai Portsmouthból származó Melissa Elliott kezdetben másoknak szerzett slágereket, elsősorban jó barátnőjének, a később repülőbalesetben elhunyt Aaliyahnak, ám igazán csak a saját lemezein mutatta meg, mire is képes. Mindjárt a bemutatkozó albumával, az 1997-es Supa Dupa Fly-jal letette a névjegyét a hiphop (és az R&B) világában, és a lemez kapásból a műfaj egyik legfontosabb darabja lett: Missy rögtön a hiphop legelismertebb női előadójává avanzsált, míg Timbaland újszerű alapjai és széttört, lelassított breakbeatjei rövidesen az elektronikus tánczenei berkekben is ismertté tették a producer nevét.
Mindehhez társult a videoklipek sajátosan futurisztikus látványvilága (nem is beszélve a duci Missy bizarr kosztümjeiről), és Missy Elliott máris fogalom lett, lemezei hangzását pedig a fél világ próbálta utánozni, legyen szó akár rapperekről, akár pedig az R&B sztárjairól. Mindez nem volt véletlen, hiszen Missy rapperként is és énekesnőként is elsőrangú teljesítményt nyújtott.
A két évvel később megjelenő Da Real World képes volt megismételni a debütálás sikerét, és további slágerek is születtek a lemezről (She's a Bitch, Hot Boyz, All N My Girl), míg olyan vendégek működtek közre rajta, mint például Eminem vagy Big Boi az Outkastból. Ezzel egy időben Missy a Gap és a Sprite reklámjaiban bukkant fel, híresen telt ajkai pedig a Face magazin címlapján. Utóbbi például olyan mély hatással volt Damon Albarnra (Blur), hogy még a saját lányát is Missynek nevezte el.
Innét azonban még mindig vezetett feljebb is az út, és végül Missy harmadik lemeze, a Miss E...So Addictive nemcsak igazi világsztárt faragott belőle, de egyszersmind pontot is tett annak a lineáris folyamatnak a végére, amit az első három album jelentett. A Get Ur Freak Onnal a legnagyobb slágerét produkáló Missy ezzel a lemezzel teljesítette be a korábbi ígéreteket, és hamarosan világossá vált számára, hogy változtatnia kell valamin, hiszen addigra már rengetegen nyúlták Timbaland védjegyszerű alapjait is. Így aztán a 2002-es Under Construction radikális újításként az oldschool hiphop zenei világához nyúlt vissza, és szövegeiben is kifejezte vágyakozását a hőskorszak iránt, amikor még a rapperek az erőszakot dicsőítő életforma helyett csak a zenére koncentráltak.
Az Under Construction dupla platina státust ért el Amerikában, és talán nem túlzás ez Missy Elliott pályája eddigi csúcsának nevezni, amit a rengeteg elismerés, díj is jelzett. Ezt követően azonban porszem került a gépezetbe, és a This Is Not A Test! című, soron következő album a karrier legkevésbé sikeres állomása lett. A kritikák most először voltak nem igazán kegyesek, és a Pass That Dutch című sláger ellenére is csak kevesebb mint 700 ezer fogyott a lemezből világszerte.