I'm currently working on a code base that has many classes that implement a Start method. 
This seems like two-phase construction to me, which I had always considered a bad practice.  I can't tell the difference between this and a constructor.

When is it appropriate to use a start method instead of normal object construction?

When should I prefer to use the constructor?

Edit: 
I don't think it is that relevant but the programming language is C#, it could equally apply to Java or C++

A Start() method (like Run(), Execute() or anything similar) is appropriate when the cost of constructing the object is low, but the cost of using it is high.  For example: A class which encapsulates a best-path-optimization algorithm.  It's trivial to set it up with a set of parameters (X squares by Y squares, with suchandsuch evaluation method), but it may take a while to execute.  If you want to create 20 of these objects, you may want to delay execution until all of them have been created - this lets you parallelize them easier, for example.

Alternatively, it could be useful when you don't know when the object is going to be needed to start - perhaps because it's based on user input, or logic which selects from a list of possibilities.

This assumes, of course, that Start() is the useful method on the object, and not an equivalent to an Initialize() method.  If it is just an extra way to set more parameters, it shouldn't exist.
