Perez debuted in WWE's then-developmental territory OVW in March 2004, being placed in a storyline as John Hennigan's ex-girlfriend. The storyline had Matt Cappotelli introduce her to the ring as a way to taunt Hennigan. Melina, however, turned on Cappotelli and aligned herself with Hennigan, who later changed his ring name to Johnny Nitro. Soon after, the duo began teaming with Joey Matthews, later known as Joey Mercury. The trio became known as MNM and on November 10, Melina managed Mercury and Nitro to win the OVW Southern Tag Team Championship, holding it for over two months. During her time in OVW, Melina, Nitro, and Steven Adkins came up with Melina's trademark split ring entrance.