I should note that there is sometimes a bit of a misconception about premature optimisation.
Avoiding premature optimisation doesn't mean that you ALWAYS just start with the simplest thing that could possibly work. For example, say you are starting out writing what is planned to be a very good chess AI.
You do your research and discover that other people have already studied this area and determined that the only way to get things fast enough is to use bit-boards. Starting out using bit-boards, which is more complex that a straightforward solution, is thus not a premature optimisation. It's an informed need for optimisation, and the only known way to get the required performance.
You either profile then optimise, or you research then optimise, or both.