This is The Twelve Kingdoms (十二国記 or 'Jūni Kokuki', 2002).
One of the major stories of the series centers around a red-haired girl named Youko Nakajima from Japan who is suddenly transported to the world of the Twelve Kingdoms and searches for her destiny. However, neither the series nor the anime concentrates solely on Youko and they do tell stories of other characters. The anime uses Youko as a framing device for telling other stories while the novels do not.
Each of the Twelve Kingdoms has a monarch and a Kirin, a mythological beast who first selects and then serves the monarch of his or her kingdom and can assume human form. Though only a few rulers and Kirin are in the main focus of the story, many are encountered in the series and play a significant role.