After returning from an assignment in the Paradas system, O'Brien notices that everyone on the station is treating him differently. His wife, Keiko, acts strangely distant towards him and meets secretly with Sisko, while Ensign DeCurtis has been ordered to realign the station's security net without O'Brien's knowledge. Things get stranger when Bashir insists on giving O'Brien a physical, and Sisko orders him to submit to the examination. O'Brien then meets with Sisko in his office, and Sisko questions him about his experiences with the Paradas, who are preparing to arrive on Deep Space Nine for peace talks. He is surprised when, instead of having him work to prepare the station for the Paradas arrival, Sisko orders him to repair the upper pylons, which O'Brien had fixed just before he left.
Later, Ensign DeCurtis refuses to allow O'Brien to check the quarters assigned to the Paradas, explaining that only Kira has the access codes. Sisko orders O'Brien back to the upper pylons. Suspicious, O'Brien pretends to leave, but secretly watches as DeCurtis enters the quarters without Kira's help. He then returns to his quarters for dinner, where he is overcome with the unsettling feeling that Keiko is not really his wife.
After Keiko goes to bed, O'Brien searches the computer for any anomaly aboard the station that could be causing the crew to turn against him, and learns that he has been denied access to all logs dated after his return from the Paradas system. He also discovers that his logs, even his personal ones, have been analyzed by other crewmembers. At this point, Odo returns from a trip to Bajor, and O'Brien is thrilled to finally have an ally. However, when Odo summons O'Brien to the Security Office to discuss what he has learned, O'Brien quickly realizes from Odo's distant tone that he, too, is now in on the conspiracy. O'Brien prepares to leave, but is stopped by Sisko, Kira and Bashir, who is wielding a hypospray. Thinking quickly, O'Brien steals Kira's phaser and escapes into an airlock.
O'Brien transports to a Runabout and finally makes his escape in a hail of phaser fire, despite Sisko's orders to remain behind. O'Brien then contacts Admiral Rollman to tell her about the conspiracy, but she, much to his dismay, is apparently also a part of it. Realizing he has nowhere else to turn, O'Brien decides to look for answers where his troubles began — in the Paradas System.
With a Runabout in hot pursuit, O'Brien heads for the Paradas system and manages to elude his would-be captors. When he learns that three passengers have beamed from the Runabout to the surface of Parada II, he follows, and finds Sisko and Kira meeting with Coutu, a rebel Paradas leader. The suspicious O'Brien attempts to shoot Coutu, but a guard shoots and fatally wounds him. As O'Brien lays dying, he is shocked to see another O'Brien appear in the room with Bashir. Coutu explains that this is the real O'Brien, who was captured and held hostage during his Paradas mission. The O'Brien who returned to the space station was actually a replicant who was programmed to assassinate someone at the peace talks. The false O'Brien dies, finally knowing the truth.