In the year 2367, Medoxa was part of an away team that discovered the Protean Codex. From the team of five, only Medoxa and two others, Jadzia Dax and Axael Krinn, survived the encounter. However, Medoxa was permanently maimed, her brain losing one of its five lobes. She was left without the ability to dream or procreate and was considered a ghost among her people.
In 2375, Captain Medoxa was the commanding officer of the Federation starship USS Anansi. Medoxa asked Ezri Dax for help when Krinn took hostages and was attempting to use the Codex. (DS9 - Prophecy and Change short story: "Chiaroscuro")