At my Publixes* in the Southeast the tortillas are in the “Ethnic” aisle instead of their more obvious place with the breads since they are both a staple starch. Also at the Publix I shop at the most it would make even more sense because the bread aisle is also the snack aisle replete with potato chips and tortilla chips so it should just be the “starch” aisle.
*Publices? 
When I was a kid in the 1970s we regularly went to a Mexican restaurant whose name I can’t recall, but do recall how much I loved their enchiladas.
Man, now I want some…
Ah, yes, Chi Chi’s! I believe they still have a few international locations left, but I’m pretty sure all the Chi Chi restaurants in the US have been gone for some time now. That said, they still market a salsa which can be found in pretty much any grocery around here (Chicago.) They were basically like the Olive Garden for Tex-Mex food (in fact, the Chi Chi’s that used to be here on South Cicero Ave. became an Olive Garden some time in the early 90s and still remains.)
I grew up here in the late 70s-80s, and always remember Mexican food being around. In the 80s, you had to go a little out of the neighborhood to find good examples of it, though. Now, the neighborhood is almost 90% Mexican, and there’s almost nothing but Mexican restaurants here, specializing in everything from goat to seafood to tortas ahogadas to enchiladas to tacos al pastor to everything else. But that is more the result of the neighborhood demographics changing. You could find most of this stuff if you headed a bit north of my neighborhood back in the 80s.
For where I grew up (central WI), it would be the late 70s. I think Taco Bells were around, but they were yucky. Mexican food day in the school cafeteria was double yucky. Swanson Mexican TV dinners were yucky.
Then we found Chi Chis (and Taco Johns). Despite being described as “the Olive Garden of Mexican restaurants”, Chi Chis was good. That seemed to be about the time Mexican food “took off” in popular consciousness.
PS not everything “authentic” is good. I ate at a family-run Mexican restaurant in Santa Rosa NM that was worse than a 70s Swanson TV dinner. You’d think am authentic NM family could could authentic NM food, but you’d be wrong.
In addition to Jose&Tony’s in Dormont, there was a Mexican Restaurant in Station Square in 1979. It’s driving me crazy trying to remember the name. They had decent food, a step or two above Jose&Tony’s. I remember liking an open face burrito type dish that was topped with a fried egg.
In Anderson, Indiana Taco Tico restaurants popped up about 1975. Taco Bell showed up soon after, so I’d say about then. Taco Tico was better than Taco Bell because they had tamales!
Olive Garden is perfectly fine, too. The description is meant to simply say that it’s a mass-market mainstream take on ethnic cuisine. As a family, we didn’t eat out much, but Chi Chi’s was one of our usual spots.
In the whitey small Ontario city in which I grew up, circa early 1980s I recall seeing something with jalapeños on it.
Not only did I not know what they were, I had no idea how to pronounce it. I think we got our first Taco Bell about 10 years later. If you can call that Mexican.
Oh, I agree! I defend OG here on the boards. My wording was poor in my post.
Same here. But I didn’t move to the East Coast until later in life, and by the time I got there there were Mexican (sort of) restaurants all over. Chi Chi’s, which the OP mentioned, and Borders if anyone remembers that and a few other chains. I think I started to notice New Mexican green chili appearing in the early 2000’s as a thing you could get in some stores and on some menus. Things like Taco Bell though, I recall being in various places on the East Coast in the 90’s. I’m not sure about the North West…I seem to recall going to Seattle in the 90’s and there being a few Mexican restaurants, and I don’t really know about the mid-Northern states, which I presume would have been the last hold outs (the Dakota’s, Michigan, Wisconsin, etc). I know that there are some good Mexican places in some of those today, but I wasn’t really up that way in the 90’s or earlier.
That’s a Tex-Mex version of an enchilada, probably Americanized. My dad went to college in New Mexico and has spent a lifetime perfecting his red enchilada sauce, which is foundational to this version of an enchilada. Layered with meat between warm corn tortillas, covered generously with the enchilada sauce and cheese, then shredded lettuce with the fried egg on top.
They are forever a part of my childhood – though I’ve never found this version in any restaurant. But then, I’ve never lived in New Mexico. 
Avery has to be pretty happy about that.
Food show on NPR talked about this very topic yesterday.
Taco John’s actually started in Wyoming in 1969. I think that’s the first experience I had with Mexican food back in the early 1980’s here in South Dakota.
It happens; the very blandest, worst barbecue I’ve ever had was right in the middle of Central Texas- Temple, in fact.
We had Zapata’s/Zantigo/Taco Bell in Minneapolis by the early '70s. There was also a gen-you-wine Mexican restaurant across from the Hi-Lake shopping center that I always wanted to try, but never got around to. 
This was pretty much my experience, too. There were a few pretty good ones, a few so-so ones. You might have to drive a ways to get to one. Staring in the 90’s, really good non-chain or small chain (2 or 3 restaurants in the chain) restaurants started springing up everywhere. Now it’s hard to drive to one without passing another on the way.
Off topic, everything I wrote goes for Indian restaurants too.
Chi-Chi’s were pretty bad as I remember. The chips seemed to come out of a bag, and the salsa came in bowls that held about two ounces and tasted vaguely of soap. We loved another chain called El Torrito because you could take kids, get magaritas, and the Arroz Con Pollo was pretty good. And they had a brunch on Sundays. I don’t really know where Taco Bell fits in. They do a perfectly good bean burrito and everything else is awful. Plus they coming up with new awful things to push. You get sick of saying “No thanks, I just want two bean burritos with red sauce” over and over again.
When I moved to Colorado in 1974 there were plenty of Mexican restaurants, many of them quite authentic. I suspect they had already been common there for years. When I lived in Washington DC starting in 1987 they were routine.
I’m sure I had Mexican food in the East long before I moved to Colorado, but I don’t recall any specific restaurants in New York. As AHunter3 says, the “Latin” restaurants in New York mainly had Puerto Rican food (and many were run by Chinese). However, one “Mexican” item could be found on almost every greasy spoon menu in the East from at least the 1950s on was chile con carne.
Suburban Cleveland had Mexican restaurants in the mid-seventies; my little hometown had a fancy, sit down place owned by a woman from Mexico City. It was nice enough that going to Marcelita’s was a special treat. I especially remember when a friendly waiter gave me a then-exotic Tecate beer can, for my collection.
The next town over had a hole-in-the-wall burrito joint that was another childhood fave. And I can remember my mother making quesadillas for dinner. So in the 1970s, in my experience, Mexican food was only slightly exotic - rather as Thai or Indian cuisine is now.
Well, duh. Real barbecue can only be found east of Goldsboro, North Carolina. Texans are uncivilized savages who think that you can make barbecue out of cows. It’s just sad.
::ducks and runs::
I was born in California in 1971, and lived there until I was 33. So my answer is “since always.”
I don’t recall Chi-Chi’s at all, it must not have made it to California(?). Taco Bell is the McDonalds of Mexican food; a different animal. If you want actual Mexican food, you don’t go to Taco Bell. But sometimes I loves me some Taco Bell. El Torrito and Chevy’s are the Denny’s or Applebees of Mexican food… they’re ok, but you’re almost guaranteed to get a better meal at a mom & pop type of place.