Nahida was last seen at her home in the 4000 block of Menomonee River Parkway in Wauwatosa, Wisconsin on October 1, 1976. She was babysitting her two-year-old niece at the time. Investigators found the child unattended in a playpen. Frozen meat was thawing in the kitchen, more food was on the stove, and a half-empty cup of coffee was found also. Nahida left behind her purse, keys, clothing and shoes; the only items missing were her robe and slippers. She has never been heard from again.

Nahida was going through a contentious divorce at the time of her disappearance. Her husband, Fahmi "Sam" Khatib, raised their son alone and told the boy his mother had abandoned him, but authorities never believed Nahida left of her own accord. She is described as a devoted parent who would not have abandoned her son. She was reportedly afraid of her husband. She had been living in the Wauwatosa area for ten years prior to her disappearance, but she was socially isolated and didn't know many people. She did tell her neighbors that Fahmi wanted to kill her.

During the divorce proceedings, Fahmi claimed his net worth was $150,000. Nahida asked the court to audit him, claiming he was actually worth ten times what he was saying. He had been arrested for receiving stolen equipment at his stereo store and for participating in a staged burglary at a friend's business. After Nahida's disappearance, Fahmi he was indicted for food stamp fraud and conspiracy, and possession of two unregistered, silencer-equipped pistols. He eventually moved to Texas.

A suspicious car was seen in Nahida's driveway the day she disappeared; it was later linked to one of Fahmi's relatives. Nahida's sister said she would have never opened the door to someone she did not know. Fahmi obtained a default divorce from Nahida in 1976 and then remarried. He died in 2001. He is still considered the prime and only suspect in Nahida's case.

Part of a human skull was found in the Menomonee River in April 2008. The river runs across the street from Nahida's house. Testing proved the skull was at least twenty years old and was that of a female who was in her thirties when she died, which would fit Nahida, but DNA testing performed in 2009 proved it wasn't hers. Nahida was declared legally dead eight years after her disappearance. Her case remains unsolved.