Written by Nashville-based songwriter/producer Dan Muckala, along with LA songwriters Jess Cates and Lindy Robbins, this power ballad about feeling empty after a breakup marked the return of the Backstreet Boys after a lengthy hiatus. Released five years earlier, their last album of new material, Black & Blue, was a worldwide smash but left the quintet feeling burned out. In the interim, they dealt with personal and professional struggles ranging from alcohol abuse and addiction (AJ McLean checked into rehab during the Black & Blue Tour) and ill-fated side projects (Nick Carter shelved his second solo album when family issues and his own dependence on drugs and alcohol caught up with him).

By the time they returned with Never Gone, they weren't sure if the industry had a place for them anymore. "When we finally started making the record, none of us knew how we were going to fit back into pop," Kevin Richardson told Entertainment Weekly. The solution was to veer into unfamiliar territory, abandoning their trademark teen-pop sound in favor of adult vocals with a rock edge, thanks to their first use of all live instruments. Critics were aghast, but the album was a commercial success, landing at #3 in America and eventually selling over 10 million copies worldwide.

Nick Carter called this song their saving grace: "The label didn't know what to do with us. But we ended up really lucky with a song called 'Incomplete' that didn't even sound like us. People liked the song for what it was, not for the people who were singing."

Fans welcomed back the Boys, but MTV didn't. Richardson recalls: "Fans were calling in to TRL requesting our next two singles. The head of our music marketing [department] told us, 'MTV said they're not going to play it. MTV dictates to the audience what is hip and cool.' That was disheartening."

Despite the album's commercial success, the Backstreet Boys weren't operating in the same level of superstardom as their previous two albums, as many radio stations dismissed the rock-inspired incarnation of group. Carter explains: "We were still able to tour. We have a loyal following, so we were able to go out even though radio at the time said 'F--k you' in so many words. They gave up on us after 'Incomplete.'"

Joseph Kahn, who directed clips for "Everybody (Backstreet's Back)" and "Larger Than Life," is at the helm for the desert-themed music video.