The story open in Mevi, in the winter, just before the Messenger's Day holiday. The title character visits the open air market near the docks to get fresh fish for that night's supper. The fish seller is a dark-skinned woman whose legs, beneath her skirt, reveal scale patterns, though the fingers of her hands are not webbed like a mermaid's, indicating she probably has both Mermish and human parentage, something relatively common in Mevi. The woman is also selling knitted Messenger's caps, to celebrate the upcoming holiday. Clary buys several fish from the woman and remarks on the caps. The woman tells Clary that she knitted them herself, "to make a little extra money for gifts for my grandchildren." She also announces to Clary that she did not leave her out. "I know you don't celebrate Messenger's Day, but I wanted you to have one. Here. For my best customer." The woman gives Clary a purple hat with a golden sun on it. Clary is stunned because this is a symbol of the Pelan people, of whom she is a part. The woman refuses to take payment for it, insisting to Clary that she wants Clary to know that with rising sentiment against the Pelan, she wants Clary to know that there are people in Mevi who believe the Pelan have every right to live there.
Over the next few days, Clary and her family prepare for the Pelan holiday celebrating the winter solstice while others around them prepare for Messengers Day. Clary is often the recipient of snide remarks from people in town, including others her own age, who recognize her as Pelan. But each time, she reminds herself of the kindness that the fish seller showed her when she gave her the hat she now wears. On the eve of Messengers Day, Clary goes to the Pelan temple with her family to worship. On her way there, they pass a boy who looks like a Messenger from a storybook. She does a double take and he is gone. Then she shrugs it off, thinking that he is probably just a boy who is dressed up for the holiday. He looks lost, and she tries to approach him to ask if he needs help, but he runs away. Thinking that he has run away because she's Pelan, Clary, finally unable to control her anger, chases after him. Knowing the city very well, she is able to catch up to him and pin him against a wall and tells him to "insult me to my face, rather than run away like a gill-less coward!" Then she discovers that the boy is, in fact, a messenger, only not the kind that deliver presents to good girls and boys. Rather, he has a message for the mayor of Mevi, which could mean life or death for people in the city, and he must deliver it tonight. But he has no way of reaching the mayor. Clary agrees to help him. The messenger thinks that this is absurd, not knowing how Clary could help him, but she states that it would be going against the principles of her religion if she did not.
Clary and the messenger travel to several different parts of the city and interact with people of all different species and cultures, doing favors and getting information in order to make it to the mayor without getting caught by someone who might be a spy trying to intercept the message. At last, they manage to procure transportation to the home outside the city where the mayor is celebrating Messengers Day with his family. In the meantime, Clary's family, worried about where she is, have begun looking for her, and a local policeman tells them that he will search for her so they will not have to fret themselves on Messengers Day. The family informs him that they do not celebrate Messengers Day, explaining that they are Pelan, and tell him about Clary's hat.
When Clary and the messenger arrive at the mayor's house, they nearly run into the policeman. They realize that the policeman is not actually looking for Clary, but for the messenger she is with because he is a spy who intends to intercept the message. They end up pinned behind a hedge in front of the mayor's house. The policeman is very close by, and they know it is very unlikely that they can escape without him noticing, especially as neither of them has the power to turn invisible.
Clary comes up with a plan. By now, the policeman knows that the messenger he is looking for is wearing an iconic messenger hat, and that Clary is wearing her Pelan hat. Clary suggests that they trade hats and go in opposite directions. The messenger says this is crazy, as Clary and the messenger are not the same size and wearing different clothes, but Clary suggests that if they initially sneak out low to the ground, they won't be noticeably of different size, and the hats will be the most apparent part of their clothing. It will only have to work long enough for Clary to cause a distraction and the messenger to sneak around the house and knock on the back door. They decide it's better than waiting to get caught. They come out from the bushes, low to the ground, wearing each other's hats, and move as quick as they can in opposite directions, Clary toward the road and the messenger away from it. The policeman glances between them, knowing he can only grab one, and decides to go after Clary, who stand up to her full height and runs. By the time the policeman catches her and realizes his mistake, the lights are coming on in the house, and they can see the silhouette of the messenger in the window.
The policeman hauls Clary back to the police station, making various threats all the while. As he does so, they pass the fish vendor, who is leaving a basket of presents at the door of her grandchildren's house to make them think that Messengers had come. Before Clary or the policeman can do anything, she works a powerful spell to turn the tide, breaking Clary free from his grip and tying him up. Then she knocks on the door and brings both of them inside. As they cannot call the police, Clary suggests calling the mayor, though she wouldn't know how to reach him. Surprisingly, the fish seller does. The corrupt officer is taken away, and the messenger had been successful. The fish seller takes Clary home, and pausing in front of her door, Clary dares to ask her if she is actually the Pelan deity in a new form. The fish seller does not answer.