A Bit of History
To get the most out of alternative history, you should start with a clean slate. Don't begin with an idea of what you want the changes you make to result in, but let things develop as you go. This way you won't commit the crime of predestination, as well as produce a more entertaining and believable end product.
Rewriting History
Begin with a change point. This is the historical event that you want to alter. From here you can move on, racking up changes and distortions until you end at the point your game begins. There are two theories with regards to change points. On one hand you can choose a major event, such as Germany winning WWII, the Soviet Union not collapsing, or the Black Plaque not striking Europe. The other theory is to change one small thing and see what happens, such as the U.S entering WWII earlier or later, Kennedy isn't assassinated, or the L'Anse aux Meadows Norse colony survives.
Which ever way you go, the next step is to explain why that change happened. For smaller changes this is easier. The larger changes often require a host of smaller changes, pursuing all these alterations to the fabric of history can become tiresome. The earlier the change point, the greater the 'snowball' effect of changes. Unfortunately, to be believable you have to get all your ducks in a row. Otherwise, some smarty pants player is going to call you out on it, thus ruining everyone's suspension of disbelief. It helps to be well versed in history, though you do not need to be an expert. As I tell my students, conducting speculative history makes you a better historian. The more you engage in this sort of exercise, the better your grasp of how history works (and doesn't) becomes.
The World We Don't Know
Our change point is a medium sized one. There is a great tendency in alternative history to choose battles as change points. Change the outcome of a battle, thus change the outcome of the war. In the fall of 732, Umayyd and Frankish/ Burgundian forces clashed at Tours in southern France. In real history the Umayyd's were defeated and driven back. This allowed the Franks to extend their influence into northern Iberia. In effect, the Muslim conquest of Europe was checked and eventually driven back (at Grenada in 1492). In our history, Umayyd troops succeeded in killing the Frankish King, Charles Martel. This broke the center of the Christian forces and shattered Frankish resistance. The Umayyd dynasty was then free to sweep into France.
This would result in a strongly, if not predominately, Muslim Western Europe at a time when religious and political alignments where in flux. It would be easy to speculate that Islam would spread throughout Europe as it had across North Africa and the Eastern Mediterranean. Since Islam is a less hierarchal and in some regards, organized institution (at least in comparison to the Catholic Church) local sects and denominations would spring up.
With Europe tied culturally and linguistically to a wider world, the spread of ideas from India to Ireland, Mali to Denmark would be easier. The Byzantine Empire, unable to rely on other Christian nations and faced with a larger number of potential enemies, falls earlier rather than later. One could even postulate a longer lasting and more coherent Caliphate forming, uniting the Mediterranean and most of Europe into one nation. Add some unconverted barbarians on the borders (Norse, Scotti, Rus), scattered border states in the British Isles, Central Africa, Indian and Hindu Kush, as well as a rivalry with the Song Dynasty in China.
Our result is a world very similar to many fantasy and sci-fi campaign worlds. You have a common tongue (Arabic), a common faith (Islam) and common culture across a wide span of the known world. The outsider barbarians are happily large and hairy, and the foreign rivals are distant and exotic. The border states provide settings for adventure in a rough and tumble mode, a distinct contrast to the more sophisticated and urban ares of the Levant, Iberia, Italy, Greece and France. Throw in enough Arabian Nights style magic and monsters as you want, and voila: a sword and sandals campaign unlike any other, and all you did was change a bit of history.

