Though the exact probability of dealing a winnable game of Klondike solitaire hasn't been successfully calculated, it is somewhere in the area of 90% when you're able to move cards from the foundation back to the tableau and replay moves. 

This means that approximately 9/10 deals of our Klondike solitaire are winnable, although it often seems much lower since it's easy to make a wrong move early on in the game.