The keyword in "premature optimization is evil" is "premature"
Some friends of mine are working in a small IT organization, trying to adopt agile principles and methods. Recently, I sort of sold them on the "make it work, then make it fast" principle. Next thing that happened: they wrote some code, put it into production, and it proved to be too slow. Apparently, significant rework is needed now. Here is what I probably should have told them about avoiding premature optimization (and didn't).
Performance needs to be tested. "Make it work, then make it fast" doesn't say "make it work *in production*, then make it fast". The right sequence generally is "make it work, then make it fast, then put it into production".
Also, performance testing should be continuous, or at least ongoing. "Make it work first, then make it fast" doesn't mean "build the entire application first". If you are working on a story, and that story has interesting performance requirements (in my friends' case, half of their stories are probably like that), it's better to figure out performance requirements for the story, and actually test your implementation for meeting those requirements *as part of the story itself*. If for some reason it cannot be done, at least plan to do it as early as possible.
It's probably worth talking about the historical context in which it was originally observed that "premature optimization is a root of all evil". As far as I understand, it was said in 1970s. CPU cycles were an expensive commodity back then. So expensive that they were a real show-stopper for many software projects. This taught people to be extremely careful about wasting CPU cycles. And as it happens with any lesson of this kind, some took it to the other extreme and sacrificed a lot of readability for marginal gains in performance. That's what 90% of premature optimization stood for back then, and the advice behind the "root of all evil" observation was to create a readable and easy to maintain implementation first, then measure its performance, then to optimize it, if that proves necessary.
These days, the situation with CPU cycles is very different (they are cheap and plentiful), and some of us may have learned the lesson of avoiding premature optimization a little too well. To the point of avoiding optimization altogether, until the need for faster code becomes painfully obvious.
To summarize, the idea behind the "make it work first" principle is to trade maintainability for speed only when you have some proof that such a trade-off is necessary. Usually, the only way to prove it is to build something and test it. So, make it work first, check if it is fast enough as early as possible, then make it faster if still needed.