Yes. Prehistoric just means before written records. We know for a fact that language existed before written records did because we've been able to reconstruct things like Old Chinese and Proto-Indo-European. It wasn't until later when PIE split into the many child languages like Ancient Greek and Sanskrit etc that written records were coming into use.

Through the work that goes into reconstruction we can show demonstrable relationship between related languages and point to some earlier form of that language, the proto-language. This is much of what historical linguists are looking at, these kinds of correspondences that can show relatedness.

Now, we can't put times on a lot of these things. We can't say exactly when, if ever, the reconstructed form of PIE was spoken. It's possible it was never spoken that way at a single time, that the reconstruction actual represents a range of times. Language doesn't change at a steady measurable rate through which we can make predictions going back in time. But it at least shows with clarity that it did exist in some relateable form, and this form predates written records, i.e. is pre-historic.

What we can't do is say things like if Neanderthal's had language, or what it would look like. We can speculate based on brain size and what we know of anatomy, but just having the potential for language isn't the same as having language. We are still not in agreement as to where certain language families like IE first originated either. But we can say PIE existed, and at least have a rough estimate at who was speaking it. The same can't be said about Neanderthals because we don't have a bunch of extant child languages upon which to base out analysis.

So yes, there's not only evidence but certainty that prehistoric peoples had language.