Of course for most stories (mine at least) the story comes first. But I've found that as soon as I lay the story out page by page, working out what and where the illustrations will be, the story changes.
Sometimes as soon as I draw the key character (boy, pig, tortoise etc) the nature of the story changes.
A story about a smart pig which was going to be my first (currently on hold) was quite a dark story. But having drawn only a few illustrations it made me change the story - to make it much lighter and hopefully funnier than it initially was.