In early November, Diego Navaira was sitting a few feet away from Sting on the set of the Today Show, singing background vocals as the former Police front man played his latest single and an old hit, “Next to You.” Navaira and fellow San Antonio native Jerry Fuentes were there because Sting, who was in the midst of a promotional blitz for his new album, is a big fan of their band, the Last Bandoleros. Sting likes their songs, he likes their vibe, and, apparently, he likes the way their voices sound behind his.

The gig went fine, though on the video you can see Navaira struggling a bit with the eternal question of backup singers everywhere: What do I do with my hands? A few minutes later, after the show ended and the band was saying its goodbyes, Sting gave Navaira something more meaningful to think about. “He says, ‘Give my love to your dad’s spirit,’ ” Navaira remembers. “His spirit. Wow. It was such a beautiful thing for me to have rattling around in my head flying back to Texas.”

Diego’s father was Emilio Navaira III, the Grammy-winning Tejano star who made a successful mid-nineties crossover to country music and was, for a time, hailed as both the King of Tejano and the Garth Brooks of Texas. Along with Selena and La Mafia, Emilio (who went by just one name most of his career) helped prove that regional Mexican music could be a commercial enterprise this side of the border. But his career ended last May, when he suffered a heart attack and died just a few days after returning home from performing a Mother’s Day concert in Mexico. He was 53. “He did what he loved to do till almost the very day he died,” Diego says. “I don’t know if I’d have this much passion for music if it weren’t for him.”

By the time of the Sting gig in New York, Emilio had been gone for six months. But the wound still felt fresh to Diego and his brother, Emilio IV, the Last Bandoleros’ drummer. After Diego and Fuentes’s appearance on the Today Show, they flew back to San Antonio to pay tribute to Emilio at the Tejano Music Awards. For the Navaira brothers, it was important that Fuentes and the band’s other singer and guitarist, Derek James, were involved in the tribute; their father believed in the group’s promise. For the first song, the full band performed one of Emilio’s country hits, “Even If I Tried.” Then, an acoustic trio featuring the brothers and their father’s close friend Michael Morales played one of Emilio’s favorite Tejano compositions, “Mundo Perfecto.”

“When we walked offstage, as brothers and sons, something visceral, something real, lifted,” said Diego a few weeks later at San Antonio’s Bombay Bicycle Club, where it doesn’t take long for a fan to recognize him and load up the jukebox with his father’s greatest hits. “I felt a rush of relief. And, I guess, a little bit of closure. The past year has been such a blur, it was important to stop and have that moment.”

When Diego got the phone call that his father had passed, the Last Bandoleros were in Fort Pierce, Florida, the midway point of what was supposed to be a month-long promotional tour to set up the band’s first country radio single. Only a week or so earlier, Rolling Stone, in a roundup of new country artists to watch, declared that Warner Music Nashville’s newest signing represented “the next generation of Tex-Mex renegades.” For Emilio, it was a point of pride that his sons were pursuing their careers together; for most of his career he’d shared the stage and co-written songs with his brother, Raulito.

It’s impossible to overestimate Emilio’s influence on his children. “I remember being maybe four or five and seeing him onstage in front of thousands of people and noticing how happy those people were and how happy my dad was,” Diego says. “I knew right away, even then, that’s all I wanted to do.” Emilio encouraged his sons’ interest in the family business by taking them out on the road to watch him work his weekend gigs. They learned about Tejano and country from his shows but also about the music he listened to offstage—a diet heavy on the Beatles, the Eagles, and ZZ Top. “He particularly loved Van Halen,” Emilio IV says. “I’m the oldest and play drums. Diego played guitar. Dad would brag to his friends, ‘They’re my Eddie and Alex!’ For a ten-year-old playing drums, my kit was comically huge, because whatever Alex had, I had.”

In 2008 Emilio, intoxicated after a post-show party in Houston, attempted to drive the tour bus back to San Antonio and wound up wrapping it around a traffic barrier. He was thrown headfirst through the windshield and suffered major brain trauma. Hypothermia therapy, a then rare procedure that involves lowering a patient’s body temperature to put him into an artificial coma, apparently saved his life. But while Emilio was hovering between this world and the next, fans and family gathered for a candlelit vigil at the Alamodome. In a photo from that day, you can see Diego and Emilio IV, thrust into their first major public appearance, looking shell-shocked.

After nearly two years of intense therapy, Emilio returned to the stage. “We almost lost him, so when he was starting to get back out there, it just made sense for us to join his band,” says Diego, who was eighteen at the time. “It was great bonding time. How many people get to do what they love to do with their dad, who also loves doing that same thing? It became a family band. And pretty much till the day he died, we played every weekend together.”

Three years ago, while the Navaira brothers were playing with their father and their own rock-oriented side project, Ready Revolution, they got a call from Fuentes, whose backstory wasn’t much different from theirs. When Fuentes was just thirteen, he was playing $75 guitar-duo gigs with his father in bars and restaurants along the River Walk. To be closer to the music industry, he moved to New York in 2006, but he’d occasionally play shows back home in San Antonio when visiting his family. On one trip a friend suggested he hire the Navaira brothers to back him. “They sang together so beautifully, so effortlessly,” says Fuentes, and a partnership was born. The first song Fuentes and the Navairas wrote together, “Where Do You Go?” wound up being the blueprint for what would become the Last Bandoleros’ sound. It pairs Beatles-esque four-part harmonies with a punchy rhythm that switches back and forth between a Tejano cumbia pattern and a classic train beat straight out of the Bakersfield country playbook.

“Initially, I didn’t know if we were writing for other artists or for Jerry’s next album,” Emilio IV recalls. “But when ‘Where Do You Go?’ popped out, we knew we weren’t giving that away. It was special, but familiar. It was like, ‘All these things go together—why haven’t we thought of that on our own?’ As clichéd as it sounds, it seemed like all our lives led to that song.”

Following the initial writing sessions, Fuentes invited his Brooklyn roommate, singer-songwriter Derek James, to contribute. “There was a chemistry right away,” says James, who was born and raised just outside the city but, after a college trip to a Wyoming cattle ranch, fell hard for country living. He is, ironically, the band’s only Yankee and the only member who wears a cowboy hat and bolo tie. “There was also an understanding that chemistry is rare. We’d all been doing our own things, and it’s tough out there on your own. We’d all had enough near-misses to be excited about chasing something as a team.”

Not long after they finished writing and recording the core of a thirteen-song record, a Warner Music Nashville A&R rep heard “Where Do You Go?” and flew to see the band play a set at the 2015 Austin City Limits Music Festival. He offered them a contract, and just before they completed the deal, he thought to ask Diego if he was related to Emilio Navaira. “It winds up he signed my dad in the nineties to his country-crossover deal,” Diego says. “He remembers seeing my brother and me roughhousing in the studio in our pajamas.”

Just as things were heating up, Fuentes, who shares a manager with Sting, was asked to play guitar on the preproduction sessions for Sting’s new album, 57th & 9th. Although Sting wound up recording the bulk of the record in London with his own band, all four Bandoleros were called in to sing some backup vocals. “I remember at one point early on, when I wasn’t even sure our manager had played him our music, Sting turned to me during the sessions and said, ‘Jerry, what would the Bandoleros do?’ ” Fuentes says. “I was like, ‘What? Did he just say that? That’s nuts.’ ”

For the Navaira brothers, working with Sting has been perhaps the second-most-important apprenticeship of their lives. Sting is more a mentor and champion than a father figure, but there has still been plenty to learn from him. “Be genuine,” Diego says. “Be humble. Be grateful. My father was the same way. To see that kind of passion and professionalism up close is invaluable.”

Perhaps the strongest commonality between Sting and Emilio is a willingness to stray out of one’s prescribed lane. Both men made wide genre swings: Emilio toward country music at the height of his Tejano stardom and Sting from reggae-tinged pop to jazz-inflected rock and, more recently, classical music. The Last Bandoleros are similarly committed to not being pigeonholed. The difference is that they’re starting off that way, rather than pivoting later, after they’ve found success. Which may be why “Where Do You Go?” peaked at number 49 on the Billboard Country Airplay chart last summer. That’s not a bad showing—it’s been years since a band that sounds this much like the Texas Tornados enjoyed any kind of radio success—but no doubt everyone was hoping for more.

“I think what we’re learning is that when you’re forming your own lane, it’s going to take a minute for people to get it,” Fuentes says. “We’re going to have to bust our ass on the road for a few years.”

To that end, this month the Last Bandoleros begin a run of dates as Sting’s opening act on the American and European legs of his latest tour. While it’s an opportunity unlikely to help them make further inroads into country radio, it’ll put them in front of far larger audiences than they could have reached on their own. What those audiences will make of them is an open question. The very thing that the industry finds appealing about them—the Great Brown Hope that offers Nashville a chance to get ahead of the country’s shifting demographics—is the same thing that makes them a risk; they might be a little too far ahead of the country’s current demographics. “Sometimes,” says Fuentes, “we’ll meet people at the merch booth after a show who’ll ask, ‘Wait. You’re a country band?’ And we’re like, ‘Maybe?’ ”

Whatever happens this year, the Navaira brothers say they’ll sleep well at night knowing that their father, just a few weeks before he died, told them he considered their success to be part of his legacy.

“To have his blessing was huge,” Emilio IV says. “And maybe we can go and play to people who’ve never heard of him—and maybe they’ll work their way back and see where it came from. But, damn, I’d also like to have been able to turn to him and say, ‘We’re doing this thing with Sting, come check it out.’ That part hurts. We’ll just have to say hello to his spirit every night.”