Well you can start by drawing the worldmap(or the area/important spots that you would like to have) on something. This would provide a base for your world so you can make your story more connected to said world.
You could also decide how magic and technolegy will affect eachother. Will it not matter much in a cosmic sense or will it be like Arcanum(best example of the T vs M i know of)
Make sure to decide between God's or none and if there are gods are they a united(ahem) pantheon or seperate rivals?
I found this thread for you that might help. http://tvtropes.org/pmwiki/posts.php?discussion=13135185060A23379700&page=0
For me it's always better to create the world up to the point to where your story begins and then write your story.