First we ask questions that gain clarity around what we are suppose to test and what the goals for that testing are. Once we understand the scope, we break the application up into its various parts and look at different quality criteria for each part. We build a list of the tests that we might perform.

Once we have that initial list, we can start to look at the order of magnitude for each type of testing we have identified (high, medium, low). Once we know how much testing we might do for an area or type of testing, we ask ourselves how much work there may be in developing and executing that testing (which depends heavily on what approach we are taking with our testing). If you lay out your high-level estimates against the magnitude of work, you can start to get a better idea of how much testing you have in front of you.

At the end of the day, you will most likely just have to time box many test activities. You'll want to know up front where you want to cut off certain activities so you can focus on others. More likely then not, you've already got an idea about some of your constraints (time, budget, resources, etc.). Those all play a big part in the estimates, regardless of historical data.