2004 sah man sie erstmals bei Ohio Valley Wrestling. Dort war sie Teil der Storyline zu den beiden Tough Enough 3 Siegern, John Hennigan (Johnny Nitro) und Matt Capotelli. Sie unterstützte letzteren und gab an mit Hennigan zusammen gewesen zu sein. Dies sollte später im wahren Leben wirklich so sein, denn beide fanden auch privat zueinander.

Sie war Teil des Trios MNM, dem neben Hennigan auch Joey Matthews (Mercury) angehörte. MNM erhielt bei WWE ein Tryout.

Melina war dann im Dezember 2004 als RAW Diva im "Lingerie" Contest von Randy Orton zu sehen sowie im "Limbo Tanz" von Chris Jericho eine Woche später. Jedoch sollte ihre Zukunft nicht bei RAW liegen.

Im April 2005 debutierte sie an der Seite von Nitro und Mercury als MNM bei SmackDown!. Im ersten Match konnten ihre Schützlinge sich die Tag Team Titel holen.

Melina wurde dann auch selbst aktiv, als sie sich mit Michelle McCool in die Haare bekam. Sie konnte McCool bei SmackDown! am 30.06.2005 bezwingen.

Anschließend legte sich Melina mit Torrie Wilson an, was zu einem Match der Beiden beim Great American Bash 2005 führte. In einem "Bra & Panties" Match besiegte Melina Torrie.

Nach einem Sieg in einer Battle Royal bei der "Eddie Guerrero Tribut RAW" Show, legte sich Melina persönlich mit Trish an und forderte sie zu einem Women's Titelmatch bei der Survivor Series 2005 heraus. Somit einem ersten RAW vs. SmackDown! Women's Titlematch! Trish konnte sich durchsetzen und ihren Titel erfolgreich verteidigen.

Im Dezember machte sie sich an Batista ran, eigentlich nur um ihre Jungs von MNM um eine Titelverteidigung gegen Rey Mysterio und Batista bringen zu können, was aber nicht fruchtete. Anschließend verklagte Melina "The Animal" laut Storyline wegen sexueller Belästigung. Mit dem Rückkehrer Mark Henry hatte sie einen As im Ärmel gegen Batista, der eine Fehde mit ihm startete.

Die Regentschaft endete im Mai bei Judgment Day gegen Paul London & Brian Kendrick. Ebenfalls kam es anschließend zum Split von MNM, wobei Melina in Mercury den Schuldigen des Titelverlustes sah. Nitro und Melina turnten gegen Mercury. Hintergrund war hierzu, dass Joey Mercury durch den Drogen-Test fiel und von der WWE erst einmal suspendiert wurde.

Anschließend wechselten Nitro und Melina zu RAW, wo sie ihren Schützling zum Intercontinental Champion Titel bei Vengeance verhelfen konnte.