The usual perception of the original Native Americans is as moccasin wearers. Obviously, a lot of this comes from movies and TV, and most of that comes from Westerns, in which the Indians* presented are Plains Indians from the mid- to late-1800s, long after the original meetings of Europeans and Native Americans.
However, there are accounts of many of the early meetings, and it is pretty clear that Native Americans went barefoot quite a lot. Think about it: even today getting leather wet can ruin it, and they did not have as advanced tanning techniques and materials as we have today. Moccasins were relatively expensive as far as labor went, so it would make sense that somebody trying to conserve them would go barefoot when possible and only use the moccasin when needed.
For instance, Le Page du Pratz, in his 1758 “Histoire de la Louisiane: contenant la découverte de ce vaste pays” (History of Louisiana: covering the discovery of this vast country), notes that, while they did wear moccasins:
Il eſt rare que les hommes ou les femmes portent des ſouliers, ſi ce n’eſt en voyage.
It is rare for men or women to wear shoes, unless they are traveling.
Note that, back then, Louisiana encompassed what we would call the whole Louisiana Territory, so we are not just talking southern climes here. (Also note that I’m having some fun showing the original printing, using the kind of “s” that looks like an “f”. You can tell the difference in that an “f” has the crossbar extending on both sides of the letter, while an “s only has a crossbar on the left.)
Du Pratz also provided a picture of what he called “Naturels en Eté”, or “Native in Summer”:
Yup, that’s barefoot all right. (Image from Project Gutenberg.)
* These days it’s always a problem of what to call Native Americans. Most of the those I know do not mind the word “Indian”, so I will use it on occasion.