Melina a rejoint le circuit professionnel indépendant de lutte avant de rejoindre WWE en 2004.
À Vengeance, Melina perdit le Championnat des femmes à Candice et n'a pas réussi à racheter le titre à The Great American Bash.