Ultimately, your design phase should come before your implementation phase regardless. Before you've begun coding you should have a strong picture of what the interactions between your classes will be, and hopefully your interface decisions will be obvious from that.
However, if you've already written a class, and now need to refactor it to have an interface, then keep in mind that the interface is simply selecting a set of functions/methods which have a common purpose which will be needed by more than one class. If you find that there are a few useful functions with your other classes will need, then those methods would be good candidates for an interface.
Another part of interfaces that makes them really useful is if you find that there are certain parts of your class that aren't private, but that you want hidden from certain other objects, in that case, you can take the functions you want exposed, and make them an interface.
I disagree strongly with anyone who says that you shouldn't design beforehand. Coders all love to jump straight into it, and sometimes, refactoring is necessary, but a strong design phase will save you huge amounts of refactoring time later.