We know how long it took. We have a good idea when life started, and for almost all its history, it was single-cellular. Multi-cellular life is relatively fresh, and on evolutionary time scales, the progression from first eukaryotes to something resembling a basic nervous systems to basic brains to humans, was fairly quick. We have many examples of animals alive today from every part of the progression, and we know they actively use it. We know how natural selection works, that it makes small moves, and that each increment has to be net non-negative in terms of fitness (at least averaging out over populations) - otherwise it would die out instead of accumulating.

All that adds up to, yes, it's surprising evolution stumbled on our level of intelligence so easily.