For their first album of original material in over ten years, the group recorded songs written by both lead vocalists, Ray Benson and Katie Shore, alongside cover versions of tracks by Johnny Cash, Guy Clark, Paolo Nutini and others.

After the release of the band's last album, 2016's Lone Star Christmas Night, Asleep at the Wheel brought in new bassist Josh Hoag to replace David Earl Miller after 25 years.

[2] According to the group's co-lead vocalist and fiddler Katie Shore, the band recorded "close to 30 songs" during sessions for New Routes, which they then had to "whittle down" for the final track listing.

Writing for Rolling Stone magazine, Jeff Gage claimed that "On New Routes, the latest iteration of the band shows just how adaptive it can be",[4] while AllMusic's Stephen Thomas Erlewine described the album as "something a rebirth for the veteran Western swing outfit".

[6] Interviewing Benson and Shore for the website the Bluegrass Situation, Amanda Wicks suggested that New Routes contains elements of "Cajun swamp, Irish traditional music, gypsy folk, and more".