Melissa was last seen in El Paso, Texas on March 7, 1987. She went out to play video games at a convenience store off Rushing and never returned to her residence in the northeast part of the city. She has never been heard from again. Two weeks before Melissa vanished, she ran away from home after a family argument. She returned after two days, however, and authorities don't believe she left of her own accord again when she vanished in March 1987.

That same year, several other females disappeared from El Paso, and most of them were later found murdered and buried in the desert. The victims were all small, slender young women in their teens and early twenties. Melissa knew at least one of them, a classmate with whom she had friends in common. She lived in the same neighborhood as several of the victims and her parents worked with the parents of another victim. Melissa and two other girls, Marjorie Knox and Cheryl Vasquez, are still missing.

David Leonard Wood, a serial rapist who was paroled in January 1987, was later convicted of murdering six of the El Paso victims, though he maintains his innocence to this day. He was sentenced to death in 1993, but his sentence remains under appeal, as his lawyers allege he is mentally retarded. The murders of El Paso girls and women stopped after Wood's October 1987 arrest for rape. He has not been charged in connection with Melissa's case and it's unclear whether he was involved.