We're introduced to Pak Jun Do, a North Korean boy who begins life in an poor orphanage. He's convinced that the Orphan Master is actually his father and that the beautiful woman in a photo hanging from his wall is his mother.
Jun Do has heavy responsibilities at the orphanage, including naming all the new boys, portioning out the meager rations, and assigning the boys to dangerous work details. He does everything he's asked, sometimes making some morally questionable decisions in the process.
When he's 14, Jun Do becomes a tunnel soldier in the military. It's dangerous work usually doled out to orphans, who are considered expendable. After some years, Jun Do's conscripted into kidnapping work because of his skills at fighting in the dark. Even though he feels twinges of conscience—especially when he contributes to the death of an innocent Japanese woman—he does everything he's told. He's rewarded with a trip to language school, where he learns English.
Jun Do is then put to work on a fishing vessel, intercepting and translating international radio communications. He eventually forms bonds with the Captain and the young Second Mate, who share his enthusiasm for the broadcasts of two American female rowers attempting to cross the Pacific Ocean. Jun Do feels special sympathy with the night shift rower.
One day, the fishing boat is boarded by an American naval crew. The Second Mate tries to stand up to them, but the Captain intervenes. Jun Do does a very bad job pretending to be a fisherman, and the Captain decides to give him a chest tattoo like the rest of the crew so that he'll fit in better. He chooses the beautiful actress Sun Moon as his "chest wife."
The crewmembers make up an elaborate story about the Americans boarding their vessel and tell it to interrogators when they get to shore. The Second Mate is made a hero, and the crew puts back out to sea in good standing. But things fall apart.
The rowers find themselves in trouble. Jun Do and the Second Mate realize that some ghostly transmissions they'd received are really from the International Space Station, which defies their North Korean notions that the whole world is in conflict and out to get North Korea. The Second Mate, disillusioned, uses a life raft to defect—and Jun Do can't stop him.
To cover up, the remaining crew makes up a story about a second American boarding of their ship. In this version, the Second Mate is thrown to the sharks. The crewmembers give Jun Do a shark bite to authenticate the story. But this time they're not so lucky. Jun Do gets the snot beaten out of him by an interrogator—though he is later declared a hero.
Jun Do recovers at the house of the Second Mate's wife, who is waiting to be reassigned a swank new husband in Pyongyang. It soon becomes clear that she won't get her wish. Jun Do is sent on a mission to America with Dr. Song and Comrade Buc, who is Sun Moon's neighbor. They are to negotiate the return of a nuclear material detector that North Korea had stolen from Japan and the Americans had confiscated.
Once in Texas, the Senator's wife and a security specialist called Wanda befriend Jun Do, especially after seeing his wounds. Wanda gives him a special camera that will send images directly to her phone via satellite. The Senator's wife gives him a dog for his supposed wife, Sun Moon.
But things don't go well: the Koreans don't get the equipment back, and they're in trouble. Once back, the interrogator sends Jun Do with some "medics" to a prison camp in the North. He doesn't understand why he's being imprisoned.
Jun Do meets Mongnan, who photographs all newcomers and all the deceased. The medics enlist his help in draining the dying of their blood supply. Mongnan helps him gather what he needs to survive, and she promises to help him. We're told that this is the last we'll hear of Jun Do.
This section opens with a first-person narrative from someone called the Interrogator, an otherwise nameless character who performs "soft torture" on enemies of the North Korean state. He tells the story of meeting Commander Ga for the first time in Division 42—interrogation headquarters. It becomes clear that this is not really Ga, the military state hero, sworn enemy of Kim Jong Il, and husband of Sun Moon.
This guy's been brought in because Sun Moon and her children are missing, and "Ga" is the prime suspect in their murders. The Interrogator has to get a confession. We understand that "Ga" is really Jun Do when he begins to talk about his experiences in Prison 33, including his encounter with and murder of the real Commander Ga in the prison mines. Jun Do assumes Ga's identity and shows up at Sun Moon's house, ready to take on the duties of a good husband.
What follows is an intertwined narrative: we get the present timeline in Division 42 broken up with the recollection of what landed "Ga" in the torture emporium. It turns out that the Dear Leader is okay with Jun Do pretending to be Ga—he needs "Ga" in order to pull off a visit by the American Senator and crew, who will be trading the nuclear material detector for the kidnapped American rower. "Ga" meets the imprisoned woman and takes her picture with Wanda's camera.
In the present timeline, the Interrogator takes his crew into the "sump," a dungeon beneath Division 42. Here, we meet Comrade Buc, who has lost his entire family and has been tortured. He tells them that Sun Moon was not murdered; she simply "flew away"—that is, she defected to America. The Interrogator doesn't believe him. Buc will eventually take his own life by eating peaches tainted with botulism.
Sun Moon and "Ga" begin to have a real relationship, after initial hesitation. At an official shindig, the Dear Leader declares Jun Do to be the real Commander Ga, which makes him Sun Moon's official replacement husband. "Ga" tells Sun Moon how he killed her husband in the mines.
As the Interrogator's character develops, we realize that he is a lonely and miserable person. His aging mother and father, already paranoid that they might be denounced, are terrified of their torturer son and don't treat him as family. When he gets hold of "Ga's" cell phone, he realizes that he would have nobody to call even if he could. He begins to have an identity crisis.
Back on "Ga's" timeline, we see that he's really bonding with Sun Moon and her kids. They go to the Martyrs' Cemetery, where he confronts the bust of Pak Jun Do, his namesake. He tells the children stories that they love and teaches them survival skills, really acting the part of a father. "Ga" also remembers the death of the Captain, who dies at his hands in the prison camp. He is devastated by this loss.
The Interrogator's life begins to fall apart in a big way. He's mysteriously losing members of his team, and he understands that things aren't as the state says. He and his team visit Buc's and Sun Moon's houses and find very little. But he does understand that Sun Moon had come to love "Ga," and he is baffled by this. He questions "Ga" about how he managed to get Sun Moon's love.
"Ga" makes discoveries around Sun Moon's house: a hidden laptop, cigarettes, and so on. He and Sun Moon watch Casablanca, a movie he brought back from America. Sun Moon realizes that she, like Ingrid Bergman's character in the movie, must leave the country. She and "Ga" make plans to defect.
When "Ga" visits Buc at the Texas-style ranch they're constructing for the American visit, he tells him about the upcoming defection. Buc is furious, because now he's implicated. He convinces "Ga" to stay and take the rap for Sun Moon's defection.
At the last minute, the ranch has to be moved to the airport, since the Americans won't leave the tarmac. "Ga" and the Dear Leader visit the rower again. This time, the Dear Leader confesses that he'd like to keep the rower for himself. "Ga" takes the opportunity to get a message to Wanda about Sun Moon by having the rower write a note and taking a picture of it.
The Dear Leader informs Sun Moon that she will perform for the Americans, and he gives her a guitar. He also makes her clean up the American rower. The two women pour their hearts out to each other, but neither understands what the other is saying.
In the present timeline, the Interrogator wants to visit the former site of the Texas-style ranch because he thinks that Sun Moon's body might be buried there—but his intern Jujack is hesitant. His more brutal intern Q-Kee senses that Jujack's keeping information from them.
When they don't find anything, Q-Kee denounces Jujack to the Pubyok and then kills him during a torture session. They learn that the ranch had been moved to the airport and that Sun Moon disappeared from there. Q-Kee now becomes Pubyok, and the Interrogator is totally alone.
Sun Moon and "Ga" spend their last night together before her defection. He wants to tell the children his real life story, but it doesn't work out. The Dear Leader summons Sun Moon, and "Ga" is crushed—he's worried that the Dear Leader will "touch her." We learn that the Dear Leader has gifts for Sun Moon: three dresses to wear for the Americans, the promise to finally show her last movie and have her mother at the premiere, and three new movies for her to star in.
Moreover, the Dear Leader wants his old relationship with Sun Moon back. When Sun Moon returns, she tells "Ga" her story so that she can be intimate with him. And then they get intimate with each other. Sun Moon senses that "Ga" won't be going with her.
The disillusioned Interrogator flees from Division 42 for a week. When he returns, he sees Commander Park and soon learns that Park's cut the tattoo off "Ga's" chest. He also learns that "Ga" will be branded with a huge, Texas-style cattle brand in the soccer stadium at dawn.
The Interrogator makes a quick decision. He returns home and feeds his parents the remaining can of botulism-tainted peaches and then returns to Division 42. He won't allow the officials to have either "Ga" or himself, so he hooks them both up to the "autopilot." He intends to erase both their identities and give them a new life, but he sees "Ga" crank up the voltage to a lethal dose.
We now get the final scene at the airport. After singing for the Americans, Sun Moon and her children are stowed in barrels meant for food aid and are carried toward the American plane on a forklift by Comrade Buc. But there is a commotion. The American rower panics and makes a run for the plane. The Americans bolt, and Buc races toward the plane, only to be stopped by Commander Park. "Ga" sics his dog on Park, which frees Buc—but then the dog is shot.
Finally, the Dear Leader realizes that Sun Moon is missing, and "Ga" tells him that he's taken the "ultimate" from him. And that's when "Ga" is sent to the Pubyok to be tortured. He feels immense satisfaction at having determined his own life course for himself, even if it did mean losing Sun Moon.
In the end, we get the state version of Sun Moon's disappearance and Commander Ga's heroic death. The Propaganda boys depict Ga as a super macho hero who chases down Sun Moon's plane and clings to the wings as it ascends with a kidnapped Sun Moon inside. At Sun Moon's suggestion, he uses his body as a missile to attack an American naval vessel in the ocean below. The voice on the loudspeaker encourages the citizens to cheer up: after all, Ga will get a bust in the Martyrs' Cemetery and be a hero of the state for all eternity.