Legend is told from the perspective of two leading characters: Day, a renegade from the streets, and June, an elite student at Drake University and the Republic's shining prodigy. Day is a criminal on the run for stealing from the Republic and making the government look foolish. In the beginning, he's watching his family from afar (they think he's dead) and he sees that his house has been marked with a strange cross. This signifies that they have the plague. Because of this, Day decides that he has to go steal plague medicine from the hospital for his family.
At the same time, June is attending Drake University and has completed three years even though she's only 15. Her parents are dead, so her brother, Captain Metias Iparis, raises her. He tells her that he's going to go on a mission that night to oversee the lab shipments at the hospital. While he's there, Day breaks in and doesn't find any plague medicine.
He runs into Captain Iparis and stabs him in the shoulder before escaping, leaving Iparis wounded. Meanwhile Thomas, the other soldier in Metias's regiment, appears at June's door to tell her that Metias has been killed. She goes to the hospital in a haze of grief, where Commander Jameson lets her see the body and tells her that June's going to graduate from college early and will become a part of the military immediately. Her first task will be to hunt down Day, which she readily accepts.
Day wakes up in a strange man's house. His friend Tess brought him there so that he could recover from his injuries, but they have to leave right away when they hear that someone is asking around and looking for him. The person apparently says that he has plague medicine and will give it to Day if he meets with him.
Day knows it's a trick, but he still has to ask around—just in case he can get information on how to find the cure. He asks a cute bartender named Kaede and gets details about where the mysterious person is saying the meeting spot will be.
He goes to the meeting spot and talks to June briefly, though they both hide themselves. From the brief conversation June gleans that Day is probably from the Lake sector and goes there in disguise as a street beggar. She runs into Tess and Day during a fight when she saves Tess, though Kaede stabs June. Day and Tess take June in but she doesn't tell them her name. She and Day start to get closer and closer—even getting a little romantic—though she doesn't know his name either.
One night they kiss, and after Day falls asleep she sees him grab at his neck even though there's nothing there. That's when she realizes that the boy she's just kissed is the one she's been hunting down this whole time. The next morning she follows him as he goes to visit his family—which confirms that someone in his family does need plague medicine.
She calls Thomas and they set up a raid at his family's house to capture him. When June tells Day that the soldiers are coming to get his family, he falls right into her trap and rushes to save them. He's too late though, and they surround the house. When he doesn't come out right away, Thomas shoots his mom in the head and Day rushes out screaming. He also realizes that June was the one who set him up. What a bad, um, day.
When Day comes to again, he finds that he's in custody. His brothers John and Eden are also in custody. Commander Jameson, Thomas, and June start to interrogate and even torture Day before his sentencing date—at which point he's scheduled to die by firing squad. All the while, June is starting to have doubts about whether or not it was right to take Day into custody. She feels bad about his mom, and she also believes him a little when he claims that he didn't kill Metias.
The truth eventually comes out when June reads Metias's journals. It turns out he left a secret message for her that leads her to his blog; in it he chronicles how he found out that the government engineers the plagues and that their parents were killed by the government. She realizes that Thomas was the one who killed Metias after all. It wasn't Day.
With this realization, June decides that she can't support the Republic anymore. She has to help Day escape. To do so she enlists the help of Kaede and Tess who are both wary of her but decide to join in. During the entire time that Day has been locked up, the crowds have started rioting and the Republic is nervous. June and Day are also getting closer, and Thomas is getting a little suspicious. Because of this, Day's execution date is moved up and June has to carry out her escape plan before they're fully ready.
When they bust out at the last minute, they almost get caught—but John rushes in to swap out with Day because he looks almost exactly like Day. June and Day escape, but John is executed in place of Day, and the Republic reports it that way. In the end, Day and June decide that they're going to go to the waterfront together and get Eden. After that, they'll travel into the Colonies and join the effort to fight against the Republic.