Fire in the Mist is the story of Faia Rissedote, who as the story begins is a shepherd from a small village. Faia returns from tending her sheep to find everyone in her village dead from the plague. In her anguish, she loses control of her magic and destroys the entire village.

This act is felt even in the far away town of Ariss, where staff of the university that exists there to train mages travel to the village to see what happened. They find Faia and bring her back to their university. Faia does not fit in there, as she is a much stronger mage but has little control; the other mage students either don't believe in her power or dislike her for being from a humble background. She does meet and sleep with a young mage, which is expressly forbidden as sex is supposed to be harmful to magical talent.

A series of murders occur; primarily targeting young mages with potential. The women at the university believe it to be the work of the men, as the murders resemble a much earlier legend which implicated the men. Faia's body is taken over by the spirit of the murderer, who it turns out was actually a woman (and is the same person from the legend) and proceeds to start killing the mages of the university. Faia defeats the murderer by surprising her with the fact that she (the murderer, in Faia's body) is pregnant, and regains her body. She escapes the university, the staff of which still bear a grudge against her, in spite of explanations, and begins to travel.