John Mellencamp closed out the '90s riding one of rock's most impressive hitmaking streaks — and still just as determined as ever to make records his way.

That approach ended up taking him a little extra time during the sessions for what became Cuttin' Heads, released on Oct. 16, 2001. After recording for years in Indiana, Mellencamp decided to pick up stakes and decamp to Florida for the earliest sessions, only to discover he'd had the right idea all along.

"We could literally walk out of this hurricane shelter and walk three minutes and be on the beach, and I think the music kind of suffered because of it," Mellencamp told MTV. "The music just kind of smelled like Jimmy Buffett, which is a bad thing. I didn't believe it could happen, but it did."

Taking two abortive passes at the album set Mellencamp back a bit, but even after he returned to Indiana, the album came together slowly, sliding back on the release schedule for months while he tinkered with the songs. For awhile, it seemed like the title might be the only thing he really knew he liked about the record.

"The blues guys back then, on the weekend, would play on the street corners," he told the Las Vegas Sun News. "One guy would play on one corner and the other guy would play on the other corner, and the one that drew the crowd and made the most money won. It was called 'cuttin' heads.'"

The difference with Mellencamp's Cuttin' Heads was that by 2001, he was really only competing with himself — and evolving a legacy he'd already well established years before. But unlike a lot of artists who have to contend with living up to the dozens of hit singles and platinum records in their discography, he insisted he actually found it easier to write new material.

"There is just so much to write about, so many paintings to paint, so many songs to write. In the late 1980s and early '90s, I thought enough songs had been written. Now, I've kind of had a change of heart," Mellencamp told Trib Live. "I can write three or four songs a day. I can't say they're any good or anything. I just say I could. I'm interested in a lot of things, and little things make it better to write about."

To Mellencamp's credit, he wasn't just writing about "little things" with Cuttin' Heads. Quite the contrary, in fact — much to the detriment of his relationship with his new label, Columbia, where he'd made his debut with 1998's John Mellencamp LP.

Listen to John Mellencamp Perform the Title Track From "Cuttin' Heads'

With the title track, for example, Mellencamp enlisted the aid of Public Enemy frontman Chuck D to talk about a subject few other rockers in his peer group would ever think to weigh in on: hip-hop lyrics and their effect on listeners and the black community.

"This is about black people selling out other black people," Mellencamp explained. "When you've got a guy on MTV or VH1 waggin' his $150,000 watch or his $200,000 necklace, saying the word 'n-----' ... suburban white kids buy these records and think this is what black people are like. He's created a new stereotype that they used to call Uncle Tom."

Race also figured heavily into Cuttin' Heads' first and only single, "Peaceful World." A duet with soul singer India.Arie, the song urged listeners to reflect on racial attitudes in America with lines like "Racism lives in the U.S.A. today / Better get hip to what Martin Luther King had to say / I don't want my kids being brought up this way / Hatred to each other is not okay."

Given the type of stuff modern mainstream acts routinely get away with singing, it might seem safe to assume "Peaceful World" would sail through the label offices with nary a shrug, but that turned out not to be the case.

"I won’t mention any names, but when this song was delivered to Columbia, one of the executives said, 'Why does Mellencamp always have a fuckin' n---er singing with him?' alleged Mellencamp in 2013. "My manager came back and told me that, and I was like, 'Get me off this fucking label. I don’t give a shit. Get me off Columbia right now.' The song came out one month before 9/11. The New York Times said it could become the 'Imagine' of our generation."

That turned out not to be the case, but "Peaceful World" made a medium-sized dent on the Adult Top 40 chart — and Cuttin' Heads peaked at No. 15, besting John Mellencamp's Billboard showing and adding another gold record to his already-impressive pile. That success, however, didn't dim Mellencamp's urge to cut his own path while speaking truth to power: his next release, 2003's Trouble No More, was a collection of largely acoustic blues and folk covers led by a reworked version of "To Washington" that criticized the Bush administration.

That album really did mark the end of his tenure at Columbia — and his following release, 2007's Freedom's Road, returned him to the Top 5 for the first time in more than 20 years.

See John Mellencamp Among Rock’s Most Underrated Albums

More From Mix 94.1