When I start working on a new logo I start with scribbling. I mostly use a pencil. Or a black felt pen. That way I can concentrate on form and typography, the two most important elements in a logo, in my opinion.
I test it inverted, in small and in large, and if it has passed all these tests, I bring in the colour.
As Kurt Weidemann, the famous German designer and typograph (*1922, creator of the CI of Mercedes Benz, Deutsche Bahn, Porsche) said: "A logo is a good logo if you can draw it in the sand with your big toe."