There are "straight" alternate histories with no fantasy element, or one so slight as to be simply the catalyst for the main action, as in "Outlander" by Diana Gabaldon, and then there is what we support, alternate history with magic or time travel so heavily entwined in the plot they cannot be separated.

First in a series about Alvin the Maker. Set in an alternate colonial America, they are written in a colloquial style which drops the reader into a place where "witches" exiled from Cromwell's stuffy England thrive in the American wilderness, performing everyday magic in order to get by. Alvin, the seventh son of a seventh son, has the "knack" stronger than anyone, and must learn to battle his great enemy, the "Unmaker", to survive and fulfill his destiny. The others in the series are:

Red Prophet (Tales of Alvin Maker, Book 2)
Prentice Alvin (Tales of Alvin Maker, Book 3)
Alvin Journeyman (Tales of Alvin Maker, Book 4)
Heartfire (Tales of Alvin Maker, Book 5)

A West Virginia town is transported back in time to Germany during the Thirty Years War, sparking a whole new version of European--and American--history. The others in the series are:

1633 (with David Weber and Jim Baen)
1634: The Baltic War (The Ring of Fire) with David Weber
1634: The Bavarian Crisis (Ring of Fire) with Virginia DeMarce
1634: The Ram Rebellion (The Assiti Shards) with Virginia DeMarce
1634: The Galileo Affair (The Assiti Shards) with Andrew Dennis
1635: The Dreeson Incident (The Ring of Fire) with Virginia deMarce
1635: The Cannon Law (Assiti Shards) with Andrew Dennis

The first in a series, a fun romp with an intelligent and very human hero. The setting is predicated on King Richard I of England (Lionheart) not dying at the time history says he did, and makes magic an accepted and useful tool for Garrett's intrepid investigator of all things weird, Lord Darcy.  

The other three books in the series are included in this omnibus:

Lord Darcy Investigates
Murder and Magic
Too Many Magicians

Critically panned but popular nonetheless, this is both time travel and alternate history, treading familiar territory in ensuring the South wins the Civil War, this time using modern weapons brought from the future. 

This book is also found in our time travel section.

Unlike "The Guns of the South," this one is pure alternate history, with the victorious South fighting a second war with the North twenty years after winning the first one in 1862. Turtledove has made himself king of the alternate history genre by taking a look at more than one era and extrapolating what might have been from his starting point of the Civil War.

Volune 1 of his Worldwar series. With the world locked in the throes of World War II in 1942, the last thing Earth needs is an alien invasion.  Yet with aliens intent on conquest swarming over the planet, humans must set aside their differences and face the threat together. Not easy, considering how difficult it is to get allies to work together, let alone sworn enemies who were at each others' throats just yesterday.