Here is a guide on the chronological order of all the Warcraft novels that are now out there. This may help you if you want to start reading the novels, and are not sure where to begin.

Rise of the Horde – Christie Golden
Covers the Draenei’s fligth from Argus, the corruption of the Orcs, the massacre of the Draenei and the events leading up to the first portal being opened.

The Last Guardian – Jeff Grubb
Covers the background of Medivh and Khadgar, Karazhan, the opening of the first portal, and the first war

Tides of Darkness – Aaron Rosenberg
Covers the Second War, the invasion of the Orcs of Southern Lordearon, the attack on Quel’Thalas, the Orc’s eventual defeat.

Beyond the Dark Portal – Aaron Rosenberg and Christie Golden
Covers the Orc’s second incursion into Azeroth, and the Allience counter-invasion of Dreanor

Of Blood and Honor – Chris Metzen
Covers the story of Tirion Fordring

Lord of the Clans – Christie Golden
Covers the history of Thrall and the formation of the new Horde

Day of the Dragon – Richard Knaak
Covers the Defeat of the Dragonmaw Clan at Grim Batol, the salvation of the Red Dragonflight and interference of Deathwing in the affairs of the Alliance

The War of the Ancients Trilogy – Richard Knaak
Covers the events 10.000 years ago of the first Burning Legion invasion, the great sundering of the world, and the hostory of Malfurion and Illidan Stormrage

Arthas: Rise of the Lich King – Christie Golden – Release set for April 2009
Covers the History of Athas, and possibly the events leading up to and including the Thid War: the  second invasion of Azeroth by the Burning legion and the devestation of Lordaeron by the Scourge

The Sunwell Trilogy – Richard Knaak and Kim Jae-Hwan
Covers the event leading up to the re-creation of the Sunwell in Quel’Thalas

Cycle of Hatred – Keith RA DeCandido
Covers the political tension between the Horde and the remnants of the Alliance following the Third war

Night of the Dragon – Richard Knaak
Covers the further machinations of the Black Dragonflight in Grim Batol, covers some of the events leading up the Blue dragonflights war on magic