Wolf's Rain, on Fuji TV
ACDB; ANN; Funimation; IMDb; Madman; TV.com; TV Tropes; Wikia; Wikipedia
It's set in the future, and wolves are thought to have been extinct for over 200 years, but there are actually wolves who walk among humans, in the guise of humans. But even in human form they can still recognize each other as wolves, even if humans can't. (They can also talk to other kinds of animals.) The four main characters in this series are wolves named Kiba, Tsume, Hige, and Toboe. They're searching for a place called Paradise, from an old legend, a place where wolves reign supreme.
Then there is a "flower maiden" named Cheza, who was created from lunar flowers, by a Noble named Darcia. However, she never awoke, and was stolen from Darcia's clan by another Noble named Oakum (or Orkham?), who gave her to a group of scientists to study, in the hopes of awakening her. The head of the scientists is Cher Degre. She has an ex-husband, a police detective named Hubb Lebowski. Lord Darcia (a descendant of the Noble who created Cheza) steals the flower maiden back after she awakens in the lab, in the hopes that she can help revive his beloved Homona (who's like comatose or something), by opening the way to Paradise. Cher leads a group of soldiers (though she eventually ends up on her own) to try to retrieve Cheza, who eventually escapes from Darcia on her own, and joins the wolves. Meanwhile, Hubb has left his job to try to find Cher. His only clue is a book she left with him, "The Book of the Moon," which contains an ancient prophecy about wolves and Paradise.
There's also a guy named Quent Yaiden, and he knows wolves exist and disguise themselves, and is determined to find them, with the help of his dog, Blue. He wants to kill all of them, because he believes wolves killed his family. He crosses paths with Hubb a few times, and eventually they start traveling together, since their respective searches are connected. (Actually, all the characters seem to keep getting mixed and matched with each other in the course of their travels, it can be hard to keep track of who's traveling with who, from episode to episode.)
There is another Noble, a woman named Jagara, whose forces kill Oakum and then turn on Darcia. And it turns out Blue is half wolf, takes on a human form, and leaves Quent to join the wolves. Eventually everyone ends up in Jagara's city, looking for Cheza, who is now in Jagara's possession. She wants to open the way to Paradise, too. She fails, and Darcia, who is now there, realizes Paradise must be opened by a wolf, and he later becomes one, himself (though I guess he always was one, just one of any number of humans who don't know they're wolves).
It's... all rather odd, and complicated, but sort of interesting, when I could follow it. Oh, and the world is coming to an end, and the closer all the characters, good and bad, come to the place where Paradise may be opened, the worse things get. It's a very bleak series, especially the last few episodes. But just when things have gotten as bad as they can possibly get, it all ends on a promising, if rather vague, note. *shrug*