I mean, sure, I’m sure that we Americans regularly have meals that consist of only pre-Columbian American ingredients purely by chance, given that we live in America.
But are there any restaurants that concentrate on food from a given tribe or region’s food tradition?
The Miccosuki Tribe of South Florida has a restaurant on Tamiami Trail, just across from Shark River Valley. You can get Indian versions of American food there. Like, instead of a hamburger patty served between two buns, you can get an “Indian hamburger”, which is essentially loose ground beef deep fried in a very dense dough, served with shredded cheese, lettuce, and tomatos. An “Indian hotdog” is a hotdog deep fried in the same dough. Both are quite delicious, but also very unhealthy (I used to have miniature heart attacks after I would eat there). They would also served fried gator.
I don’t know how “authentic” this food is. Probably not very.
In Santa Fe, New Mexico there are a number of eating places where you can get authentic native American food, and at some of the res cafes in northern New Mexico (and parts of Arizona) they will have a bunch of Navajo and Hopi specialities.
There’s at least one place in Van. BC-- Liliget Feast House-- that just does a coast Salish style menu-- fried kelp, cedar-smoked salmon, various local tubers, caribou and such. Some deserts made with soopolallie/ buffaloberry/foamberry, that are very interesting. I don’t think there are many places where one can get a soopalallie daquiri.
If I may extend the OP to include all North American Indian nations, we’ve got a few restaurants of this kind in Quebec:
From the Quebec Aboriginal Tourism Corporation
From Indian and Northern Affairs Canada, Quebec First Nations
On preview: OK, **Capybara **started it! 
There’s one in Asheville, NC. I don’t know much about it - we drove past and it was pointed out to me.
The one is Asheville is called “Spirits on the River.” It’s okay. Their menu isn’t specific to any one tribe, but they serve a lot of game, fry bread, wild rice, corn, and other indigenous North American food.
I don’t know, it sounds like it would go over pretty big at the pow-wows around here. Maybe it’s not traditional, but if you’re defining “authentic” as “what American Indians actually eat,” it’s probably a lot more authentic than frogs’ legs with maize salad (one of the "Dragging Canoe Combo Dinners"at Spirits on the River).
The Coastal Salish hunted caribou?
There’s a pretty good restaurant in the Mohegan Sun Casion called Uncas Grill that serves northeast woodland indian inspired food.
i don’y know if it’s still there, but when I lived in Salt Lake City there was a place called Yah-tah-hey Navaho Tacos in the Trolley Square plaza.
Yes, they are all over. They are called “Mexican” restaurants.
I’ve always had an idle whim to serve a pre-Columbian Thanksgiving dinner. Turkey, corn bread, cranberry sauce, pumpkin pie made with maple syrup and pecans, and so forth. I think I could pull it off.
Try the Miantonomo Steak Special. It is the best meat I have ever eaten.
My Aunt Carol (a Blackfoot indian) made these. We called them indian tacos. Man… I loved those.
Hell if I know-- I had some sort of big mammal there-- perhaps it was moose or something. Do I look like an anthropologist?
(actually, I probably do. . . but I’m not. Maybe the place is, like, first nations fusion or something?)
I stayed at a Native American-owned and -themed hotel in Santa Fe. It’s the only place I’ve been that had Native American channels on the cable. The restaurant, of course, featured native American-inspired dishes. I say inspired because I’m sure they were Americanized just as Mexican, Chinese and every other ethnic restaurant is Americanized.
The Seneca Niagara Hotel and Casino in Niagara Falls has the Three Sisters Café which features Native American food. If you ask for the special menu. It was excellent. Of course, so was their Asian restaurant. (Yes, I stopped there for the food, not the gambling. I’m weird that way.)
The Smithsonian’s Museum of the American Indian has a Cafe that serves Indian food…the Mitsitam Cafe, if you’re ever in Washington, DC.
I was planning on eating there later this summer when I visit Vancouver, but apparently the owner has retired, and the restaurant is closed. I was rather disappointed, because I had heard good things about it, and figured it would be a unique experience. Oh, well.
Probably the best sampling of native foods in the Americas. It has food from the Plains, Eastern, Caribbean and Central and South American cultures. I recommend the quinoa salad.
you could always go to a French restaurant and ask for the Sioux chef.
Took the words out of my mouth. Mexican restaurants serve mostly Native American foods: beans, corn, tortillas, tomatoes, avocado, peppers. Only the meats, the onions, and flour tortillas are European imports. (And recent archaeological discoveries indicate that chickens arrived in the New World long before Europeans. Probably via Polynesian voyagers. So really, only the beef and pork dishes are inauthentic as Native American food.)
Also, pit barbecue is a Native American cooking method (there was an article in Smithsonian magazine on this some while back, including early illustrations of Native American pit barbecues), and Brunswick stew is just a variant on traditional Indian kettle stews. (Think about the ingredients. Tomatoes, peppers, corn…) So stop at any barbecue stand, have some barbecue and Brunswick stew, with some cornbread or baked beans on the side, and there you are! (I suppose to be truly authentic, you’d need barbecued venison or turkey, or some game meat.)