The album was recorded from the end of 2008 through April 2009.The Outsiders was co-produced by the band along with Jim Scott, John Alagía, and Rick Beato, who produced portions of their previous album, The Heat.
The album's first single, "Lay 'Em Down", was released to Christian radio at the beginning of June 2009 and was released on iTunes on June 16. The next single from the album, "Something Beautiful", was released in August. The album reached #20 on the Billboard 200 and #9 on Billboard's Top Rock Albums chart.
The Outsiders garnered critical acclaim from music critics. At Allmusic, Andrew Leahey rated the album four stars, and suggested that the band "offer[s] up another collection of sweeping, reverent rock songs" on which he alluded to how the album "flirts with touches of roots rock and traditional gospel, though, from the title track's powerful Southern stomp to the sheer power of Bear Rinehart's voice." Furthermore, Leahey noted the album "covers more ground than records by similar artists, and it does so without alienating any of its secular-minded listeners, too." Matt Conner of CCM Magazine indicated in a positive review that that the album "brings even more evidence to the table that Rinehart's rock sensibilities only improve with time", and Conner also mentioned that the album's "second half provides some of the most beautiful moments on the record."
At Christian Music Review, Liz Haveman rated the album three-and-a-half stars, and criticized the album because "some of the songs are confusing in their message. They are a little too vague to really grasp what these guys are trying to say." However, she highlighted how "the music itself is really enjoyable. It has a “Jack Johnson”-ish quality to its laid back candor. Over all, the album is really enjoyable and I think it is going to satisfy the Needtobreathe fan base." Ian Webber at Cross Rhythms rated the album nine out of ten stars, and underscored how the band "have crafted an excellent collection of tracks that wrestle with issues of faith and doubt in an honest and accessible way." At Indie Vision Music, Joshua Clark rated the album four stars, and felt that the "lyrics seem a lot more ambiguous", yet called the release "near-perfect".
At Jesus Freak Hideout, Jen Rose rated the album four-and-a-half stars, and evoked that the album was "one of those rare gems where every track stands out, some pulling you in with a catchy intro or a clever lyric, others surfacing after spending time with the music." Pär Winberg of Melodic.net rated the album four-and-a-half stars, and underscored that "if you also add really good song writing to that - you all understand that you have a killer album", which he concluded with calling it "a fabulous demonstration how good music should sound like." At New Release Tuesday, Kevin Davis rated the album a perfect five stars, and emphasized that the album was "the most catchy and meaningful album [I've] heard this year."