Fly has been used for more than 400 years in metaphorical senses of "move with a sudden rush" and, by extension, "move with sudden violence". To fly out is to express oneself with sudden vehemence or anger, to fly off the handle is to lose one's temper or self-control, to fly at someone is to attack them furiously.
And face is used figuratively in a number of expressions to signify "confrontation" (note that front itself, etymologically, is the forehead and by extension the face). We speak of facing an enemy, of remaining brave in the face of danger, and of getting in somebody's face, to become personally belligerent.
So to fly in the face of something is to challenge it aggressively, to attack it, to oppose it violently.