I've read a few of the novels based on the warcraft games and really enjoyed them. From time to time I mention them here, such as when I did the lore post on Velen after reading about him in Rise of the Horde, by Christie Golden. On WoW Insider, they run a column every week called Ask a Lore Nerd, where people write in, ask lore questions, and the lore nerd answers them. This week, the column was partially about the fiction novels for Warcraft, and whether or not they were canon and which ones would be important to read.
First of all, I've really enjoyed all of the warcraft books I've read. They're all by different authors, so they each have different styles, but it's a lot of fun to read about places and characters and events and then to go and see those same things in the game. A prime example of this is Lord of the Clans, also by Christie Golden, which among other things covers the events of Thrall's escape from Durnholde Keep. After reading the book, you can then go and actually participate in the escape yourself. You actually know what the Keepers of Time are trying to preserve. When they talk about Taretha and her fate that is unavoidable, you'll know what that fate is. It provides another level of immersion, and lets you appreciate all of the work that goes into the lore of the game.
The Last Guardian, by Jeff Grubb will give you the history of Medivh and Karazhan. It's very well written and actually ties into a lot of other characters in lore, such as Khadgar and Anduin Lothar. The time period it takes place in is during the first war, AKA Warcraft: Orcs and Humans, so if you've been playing Warcraft since the first game, you'll appreciate it even more. You learn who Moroes was before just an undead boss in Kara, and there are some nice recognitions of events from the book in some of the items that drop.
Personally, I enjoyed the War of the Ancients trilogy, by Richard Knaak, but a lot of people dislike the way he writes, and the fact that his own characters seem to take the spotlight away from the more lore established characters. To some extent, I can understand this. However, the introduction to the Warcraft Archive, that includes several warcraft novels, is written by Chris Metzen, the creative director behind WoW who is responsible for a lot of lore behind the game we all play today. In that introduction he tells who Knaak, who was known for his Dragonlance novels, contacted Metzen to write a book about Warcraft. Metzen, who was a fan of Knaak's works, readily agreed, and together the hashed out a lot of the lore related to the dragon aspects. From this came Day of the Dragon, by Knaak.
Day of the Dragon would be a good read going into the Wrath of the Lich King expansion, as it deals with the Red Dragonflight, and the Kirin Tor, who will both be in Northrend for various reasons. War of the Ancients is all about the first battle with the Burning Legion and the Kal'dorei of Azhara, 10,000 years before current WoW time. What some people have issue with is that War of the Ancients involves time travel, placing characters from Day of the Dragon 10,000 years in the past, front and center with major players like Tyrande Whisperwind, and the Stormrage brothers, Malfurion and Illidan. It's hard because time travel always adds complications to a story, and it might have been better if just told from the point of view of the Night Elves rather than injecting Knaaks personal heroes into it. But I can't argue with it too much because Knaak and Metzen have worked together to create these stories and characters. And supposedly according to the Blizzard developers, all of the WoW fiction novels are to be considered canon, and part of the lore of the game.
I'm going to try and read Tides of Darkness, by Aaron Rosenberg next. It takes place after the second war (Warcraft II) and is about Anduin Lothar, someone I would like to know more about. There are a couple more books to check out too. But more than anything, I'm eager to see the next book from Christie golden.