When Sisko sees a painting depicting B'hala, Bajor's legendary lost city, is returned by the Cardassians, Sisko is inspired to search for the famed site. The painting depicts an obelisk that, according to legend, marked the city's coordinates in the universe. Sisko studies the visible markings, then recreates the obelisk in the holosuite to try to determine what the hidden markings might be. After working until three in the morning, he tries to save his work, but the holosuite system shorts and knocks him unconscious. In the infirmary, Bashir tells Sisko his brain has been overloaded, and his senses will be enhanced for a few days. The doctor lets him go, but warns him to return if he experiences any side effects. That night, during dinner, Sisko absentmindedly cuts his fruit into a series of shapes, then realizes that they are the missing markings from the obelisk. He returns to the holosuite, but is interrupted by a call from Admiral Whatley — Bajor has been accepted into the Federation, and the ceremony will be held on Deep Space Nine.
Back in the holosuite, Sisko has a vision that he is in B'hala. During the vision, he briefly understands all of Bajor's history and can see its future. Afterwards, he continues to study the obelisk, and just as he determines where B'hala should be located, Kasidy Yates, his old girlfriend, returns from prison. He invites her to accompany him to Bajor immediately, and, thrilled to be accepted back into his life, she agrees. On Bajor, Sisko is stricken with a painful headache. He ignores it, and soon finds the lost city of B'hala.
The Bajorans regard Sisko's discovery as a miracle and, for the skeptics, confirmation that he is the Emissary. Admiral Whatley, however, is more concerned that Sisko devote his energy to Bajor's admission into the Federation. He visits Sisko at the site on Bajor and asks him to come home. Sisko begs for more time, sensing that the lost city holds answers to some important questions. Reluctantly, the Admiral agrees — provided Sisko submit to a physical when he returns. When Sisko gets home, he seems to have psychic powers. Unfortunately, his headaches are getting worse.
Bashir determines that Sisko's headaches are life-threatening and asks to operate immediately. Sisko refuses, unwilling to put a stop to the visions. Jake and Kasidy are crushed, but Sisko is determined to see his visions through. He asks Kai Winn to help him consult the Orb of Prophecy, and while he sits with the powerful orb, the ceremony admitting Bajor to the Federation is put on hold. An angry Admiral Whatley finally begins the ceremony without Sisko, and the captain suddenly appears, weak and in obvious pain. He warns the assembled that if Bajor joins the Federation now, it will be destroyed by "locusts."
Sisko is then rushed to the infirmary, where Bashir grimly reports that he must operate immediately to save his life. Since Sisko himself refused the operation, Jake, as the next-of-kin, must decide his father's fate. Unwilling to let his father die, Jake goes against Sisko's wishes and okays the operation. Sisko awakens to anguish at the loss of his visions. However, he was able to convince the Bajorans to put their admission to the Federation on hold. Kasidy gently reminds him that while he has lost something very important to him, what he saved — his life with his son — is even more precious.