In classic Sanderson fashion, the beginning of this book was the part to see the biggest edits. I usually start a novel, write from beginning to end, then go back and play heavily with my beginning to better match the tone of the book.
Here, one of my big decisions was to choose between two prologues I had written out. One was with the Heralds, and set the stage for a much larger story—I liked the epic feel it gave, and the melancholy tone it set. The other was Szeth's attack on Kholinar. This was a great action sequence that set up some of the plots for the novel in a very good way, but had a steep learning curve.
I was very tempted to use both, which was what I eventually did. This wasn't an easy decision, however, as this book was already going to start with a very steep learning curve. Prelude→prologue→Cenn→Kaladin→Shallan would mean five thick chapters at the start of the book without any repeating settings or viewpoint characters.
This can sink a novel quickly. As it stands, this is the most difficult thing about The Way of Kingsas a novel. Many readers will feel at sea for a great deal of Part One because of the challenging worldbuilding, the narrative structure, and the fact that Kaladin's life just plain sucks.
It seems that my instincts were right. People who don't like the book often are losing interest in the middle of Part One. When I decided to use the prelude and the prologue together, I figured I was all in on the plan of a thick epic fantasy with a challenging learning curve. That decision doesn't seem to have destroyed my writing career yet.