If they traded for wheat flour they probably made fry bread or something like it. But since by that time they weren’t farmers any more they wouldn’t have been able to farm which means no wheat or corn.
The particular lifestyle depicted in that movie–horse mounted nomads who lived on the great plains and hunted buffalo–was very short lived. A few generations back all those people had been mostly farmers.
Wiki gives the date of its invention as 1864.
Pre-Columbus, American Indians didn’t have wheat or other major grains like rye, oats, barley, or rice.
Other ingredients of fry bread like sugar and lard are also post-Columbus (although food could have been fried in other kinds of fat.)
Wild bison are doing fine, but bison you eat in a restaurant is likely to be farmed. Ted Turner has a ranch that raises them in Montana, as well as a chain of restaurants specializing in it. There’s also “beefalo”, a hybrid of cow and bison, which is easier to raise.
As I recall, the Sioux were dog eaters. Really. I’m not sure you would find that on the menu nowadays.
Pardon the zombie, but I just came upon this thread and wanted to mention that the First Nations people in Manitoba, Canada, have adopted bannock and tea as native foods, both of which (definitely the first at least) likely came from the Scottish settlers who formed one part of the local Metis populations (though the French-and-native Metis are more commonly known). Holy run-on sentence, Batman!
Anyway, they have tea-boiling (in a large can over an open fire) and bannock-baking (also over an open fire) contests at native events in Manitoba. I don’t know how similar it is to fry-bread, which I’ve never seen; it has a very crumbly biscuit-like texture (American biscuits, not British biscuits) which leads to its description in Scottish history as ‘the moon and stars’. The moon is the big round bannock itself, and the stars are the ‘sheetful of crumbs’ it produces when you eat it. 
It’s historically made with buttermilk. If you used more liquid and made a batter instead of a dough, you’d basically have pancakes.
Bannock is very Scottish, and in Manitoba would not have pre-dated the arrival of wheat (previously oat) flour and the modern addition of baking powder, but in Manitoba it’s totally a native thing now. Surely there was something similar made from cornmeal before that, but it wouldn’t have been quite the same. Many of the existing local native traditions stem from contact with Scottish and English settlers and French traders, often adapting older habits with newer materials, like the metal bells that adorn their fancy dance costumes. Previously these would probably have been made from shell or bone. Anything to do with horses also post-dates European contact, as all the native horse species had died out long ago.
Actual local native foodstuffs would include blueberries, which grow in the northern forests on tiny low bushes completely unlike the varieties found in the States, and pemmican, which is a very rich and compact travel food made from a combination of pulverized dried meat, rendered fat, and maybe some dried berries as well, formed into patties or packed into a rawhide envelope for transport. The meat may be deer, which are common enough nowadays that I would see them in the middle of the city, bison, which is still readily available though not as common as it once was, or in the more northern areas, moose and caribou. I ate all these animals at one time or another while I lived in Manitoba. You can probably find restaurants that will serve any or all of these meats, as well as bannock, but they probably won’t style themselves as ‘native’ restaurants as such even if they’re run by First Nations proprietors. They’re just local places for local people, heh.
Of course, further north you have Inuit communities who still hunt seal, which I’ve never had and probably wouldn’t like. I hear it tastes very fishy due to their diet. They may also still hunt polar bear, though I imagine there might be restrictions on that for conservation purposes. They catch a lot of salmon up there as well. But since the native way of life up there has been largely supplanted by European settlers just like everywhere else, they mostly eat hideously expensive modern groceries shipped from the south by plane due to the lack of roads.
Brujaja mentioned acorn bread (which would probably have been a historical native food in Manitoba due to the prevalence of burr oaks) and the necessity of removing the tannins from the acorns. Probably the quickest way to do this is to shell and grind up the acorns before soaking them in daily changes of cold water over about a week. This will expose more of the meat to the water and help the tannins leach out faster. I’ve seen a suggestion to suspend a muslin bag of acorn meal in a clean toilet tank and let the flushing water leach out the tannins.
This can be accomplished ‘in the wild’ by putting the acorn meal in a hole in fast-draining sand and pouring water over it repeatedly with a cedar branch on top. Maybe there’s something in the cedar that helps to neutralize the tannins. I would think that the addition of some clean wood ashes (historically) or baking soda (modern) to the water would help, as the higher pH of the resulting solution would help neutralize the low pH of the tannins. You’d then have to dry out the meal as quickly as possible to prevent it getting moldy. Save the tannin water to tan leather, pretreat wool for dyeing, or use as an antiseptic.
Well, that turned into a much longer post than I had intended. Oh well. Hope someone found it interesting.
Frybread is the official state bread of South Dakota.
There are no Indian Reservations in Oklahoma any more, at least not like in western states.
Frybread:
Bannock:
The frybread entry says that it’s not native to the Americas at all. It didn’t exist until 1864, which the ingredients were given to the Navajos by the U.S. government when they were moved by the government to a new area that didn’t support the agriculture they practiced before. The bannock entry says that frybread is a type of bannock, although they don’t look similar to me.
Jeff Smith, PBS’s Frugal Gourmet (remember him?) did a number of shows on Early American and Native American cooking. Here’s a sample:
In one episode, he had recipes from the Plains Indians that included buffalo stew with choke cherries. I got the impression that a lot of the ingredients were not all that easy to find.It looks like the frybread uses more fat all over, apparently sometimes even deepfried, while the bannock is more of a biscuit or griddlecake. I imagine the ingredients aren’t that different these days, though bannock used to be made with oat flour, as wheat wouldn’t be that common a crop in Scotland. The wiki page says they’re similar to or interchangeable with scones, and I’d say that’s about right. Scones are basically the British version of baking powder biscuits. These days they’re made individually in a triangular shape, usually sweetened and containing raisins or other sweet things, so not quite like the bannock of old.
I get the impression that the food is focused on survival rather than presentation or complexity. It’s like trying to open a hunter-gatherer restaurant. For today’s special we have steak with a side of boiled onions.
That’s true, but at one time the food served everywhere was focused on survival rather than complexity. Also, the food that’s now considered native for nearly everywhere in the world is considerably different from that served pre-1492. I assume that you all know about the Columbian Exchange:
There has been such an enormous transfer of everything, including food, between countries since that time that the foods served in nearly any country are much different now than those served in, say, the Middle Ages. The food you would get in any sort of ethnic restaurant will include some things that were once were only found and hence only eaten in the Americas. Presentation wasn’t a big thing with most cuisines either during the Middle Ages. If someone wanted to really make a Native American restaurant popular, they should make it Modern Native American. Take some standard American Indian dishes, add some things from other cuisines, and present the dishes better. All restaurants today are really combinations of things from various places, not strictly food that’s native to anywhere for the past thousands of years.
That’s like one restaurant I went to in northeastern China. The theme was food common the Cultural Revolution, and the fare consisted solely of insects – silk worms, scorpions etc.
There’s this to consider:
Ok well if we are going to have native american cuisine as an art, there must be some prominent chef to present it on the TV. It doesn’t need to be someone who is actually native american. I recommend that guy who yells at people all the time on his show…Gordon Ramsey.
You TWAT! You call that a succotash!? It’s SHIT!