The Twelve Kingdoms, or Juuni Kokuki is an anime I grew up with and have recently watched over again. It has a beautiful story and amazing soundtrack to it and I honestly cannot recommend enough.
It is set in a world which exists in parallel to ours but much smaller with the main lastmass divided to accommodate 12 kingdoms. The world is also filled with monsters and special humans with the title of Sennin, or immortals. The title is granted by the government or the ruler, making it a normal part of the world to have people live hundreds of years if they are of rank or have their use.
Kings and Queens are the only ones automatically granted immortality from the heavens as they are chosen by a sacred animal called the Kirin. Without a ruler monsters and natural disaster plague the lands and make life difficult for the citizens. Somehow having a ruler that pleases the heavens stops all that without having to do much except being alive and ruling the kingdom in a fair way.
The story follows Nakajima Youko, a high school student who meets a strange man claiming he been looking for her and she is in great danger. Even though the beginning may sound cheesy or trying to appeal a young audience the story proves to develop quite quickly and reveal the rich lore behind the world and characters.
As she is chased by monsters, Youko and two of her classmates are taken through a portal to another world to escape. It is soon discovered only Youko can understand the language and the others have rely on her. Slowly the group discovers the world is very different from their own as they fight to survive monster attacks and people of the land who hate off-world strangers and call them Kaikyaku.
The story continues to reveal fantastic characters and explore interesting philosophies while putting different characters in varied uncomfortable situations. The show is also backed with very pretty graphics which may be somewhat more of an animated series than a japanese anime. There are very strong male and female characters and no fan service or off story episodes making this one of my favorite story telling animes.