Well, I was playing with the Egyptians (it was my second campaign) when the Horde appeared. I was expecting them so I wasn't suprised. You might think I built a huge army to defend my provinces, but instead I built assasins. You may ask why so let me explain. When they appear the Khan has no heirs so if dies his faction is eliminated and his forces become rebels. When you've killed the Kahn you can then use emissarys to bribe their armies at a very low cost (about 6000 florins for a an army). I used this tactics to conquer the Byzanteens and Novgorod.