It would have had to make a very quick start on Mars. But Mars did have an oxygen rich early atmosphere at one point, they think due to the loss of the hydrogen from its water into space. So far we don't know if there was any life on Mars at all, and on Earth at the time that Mars lost its oceans, all we had were microbes.
But we don't know if evolution on Earth is typical, or fast, or slow. Or what lead to evolution of multicellular life.
To have multicellular life on Mars so long ago, it would have to evolve very quickly. But then Mars was much colder, with probably many "snowball Mars" episodes, and multicellular life on Earth came to its own after the most recent snowball phase.
If Mars did have multicellular life early on, that changes everything as it is only 500 million years from the first complex multicellular life to us. So then - intelligent Martians billions of years ago would be possible.
Intelligence doesn't have to mean tool using. Or could be very feeble tools. Think intelligent parrots or intelligent dolphins. Even intelligent elephants, probably have some difficultly getting very far with technology. It's a little hard to imagine either dolphins, parrots or elephants even making fire.
We might be unusual amongst intelligent species to be so well adapted to be capable of technology and even for us it took long enough to get to anything more complex than fire and chipped tools.
So - I'd say intelligent native Martians seem rather improbable, because most likely it only had microbes. But if it had multicellular life early on, perhaps it could also have some intelligence as well.
At any rate doesn't seem too likely in recent past. Unless really tiny and live underground... You'd see their traces on the surface and we can see the surface of Mars with a resolution of 30 centimeters in the best mapped areas - can see it from orbit with far higher resolution than the Moon - just because we have sent more capable orbital spacecraft to Mars than to the Moon. So, no tracks or buildings or cities and a lifeform anything like us would need very advanced technology to survive on Mars.
It is also a very inhospitable environment - and similarly inhospitable places on Earth such as the Atacama desert and McMurdo dry valleys in Antarctica have microbes only. They correspond to the most hospitable places on Mars (if Mars is habitable at all which nobody knows yet either way for sure).
Or perhaps some lichens could grow there. But even if it had multicellular mobile life in the past, seems unlikely it is still there, on the surface anyway. Of course all of that is arguing by analogy with Earth life. Could be surprises but to have complex life like us it needs some abundant source of energy, and generally exobiologists think it is unlikely. And deep below the surface we do have a few small worm like creatures on Earth but no big complex intelligent creatures.