Whilst considerable research shows that people tend to underestimate their task completion times, there is little research concerning factors that mediate the time prediction process. In Experiments 1 to 3 a simple, well-structured task, the 3-disk Tower of Hanoi, showed no evidence of under-estimation; in fact, participants consistently overestimated the duration of this task. However, predictions were more accurate among participants who acquired some task experience beforehand. Task complexity was also found to be an important factor since the more cognitively complex 4- and 5-disk versions produced less biased predictions. Using a cognitively undemanding disk movement task, we found a general temporal overestimation in Experiment 4, thus suggesting that task duration might be responsible for the general lack of underestimation in the present studies. These results have implications for the planning of tasks in everyday life, and also suggest conditions under which time prediction accuracy can be improved.