Elvis Costello remembers his first visit to New Orleans. It was the third city he played on his debut U.S. tour in 1977.
"When you are a music fan and you imagine going to all of these places you've heard about and imagined in song, you want them all to be exactly like your dreams," said the 51-year-old Liverpool native. "New Orleans was very vivid — exactly as I imagined. There was music playing in the streets, and it had that amazing atmosphere.
"But it was always a tough city to play. There was so much music there already, they didn't really need a lot of help from outsiders. I would actually scheme to get my agent to book us shows anyway, hoping they would be canceled so we could just have two days off to just spend there."
Costello's deep affection for the city brought him back to record The River in Reverse with New Orleans R&B legend Allen Toussaint. The pair are on the road to promote the disc and perform live Wednesday night in St. Paul.
"It's a superb collaboration and a very real one," said Toussaint during a recent joint telephone interview with Costello. "It's not just me doing what I do as a producer. Elvis has such insight, it's wonderful to work together."
The pair have a history. Toussaint performed on Costello's 1989 album Spike and, earlier in that decade, produced Costello's cover version of Yoko Ono's "Walking on Thin Ice" for a tribute album.
They were reintroduced at Wynton Marsalis' Higher Ground Benefit, held in New York shortly after Hurricane Katrina devastated Toussaint's city and home. They performed Toussaint's "On Your Way Down" together and quickly hatched plans to make an entire album.
The result, The River in Reverse, includes seven songs from Toussaint's vast catalog, five new collaborations and the title track, which Costello wrote a week after the Katrina benefit.
"The River in Reverse was undoubtedly influenced by Allen, but it was also influenced by conversations with friends from the city and people I was meeting for the first time," Costello said. "I wrote the song very rapidly, and there are some accusatory lines in it. But it's about the way we're living generally, the drift and the feeling that we could be doing better.
"(The album) began in my mind as a song book of Allen's work, but in those first weeks after Katrina, I thought maybe we could write some more songs that speak specifically about it — even though a song like 'Who's Gonna Help Brother Get Further' is as true today as it was 30 years ago."
While anger and frustration are among the many emotions on the disc, Costello and Toussaint don't necessarily consider it political.
"There are love songs as well, but it's not an album about love," Toussaint said. "We are making music that's a reflection of the world we live in. There are things that need to be said, and what better way to say them than through song?"
Added Costello: "There are songs of celebration, too. Songs like 'Wonder Woman' that are so great to sing. There are despairing images, yet there's still hope. That's definitely the case in 'Ascension Day,' which opens very bleak and closes with hope."
In concert, Costello and Toussaint are joined by musicians from both camps, and they're performing songs from The River in Reverse alongside selections from Costello's past work.
"You'll hear new arrangements and some songs in brand-new forms," Costello said. "When you hear a couple of the songs in the show, you might get an idea as to why they're in there. Deep down, I learned something from Allen's writing a long time ago."
Outside of the business of making music, Toussaint has yet to re-establish his home in New Orleans, but he hopes to be back permanently by the end of the year.
"The recovery is very slow," he said. "There are people who want to come back but can't. They need help; they need to be reached out to. But the spirit is very good among the people who are there. In time, it will be fine."
Costello, for his part, said he's inspired by such talk. "Allen's optimism about the recovery has been remarkable. He's so stoic in the face of his losses. But he has moved forward and taken this as an opportunity to do new things. It would be crazy to respond with gloom and despair."