Newsboys perustettiin vuonna 1985 Mooloolabassa, joka sijaitsee AustralianQueenslandissa. Yhtyeen perustajajäsenet olivat Peter Furler, George Perdikis ja Sean Taylor. Pian tämän jälkeen myös John James tuli mukaan yhtyeeseen solistiksi.
Vuodenvaihteessa 1986–1987 yhtye siirtyi Yhdysvaltoihin. Demonauhan He's Coming Back jälkeen Newsboys julkaisi vuonna 1988 debyyttialbuminsa Read All About It, joka ilmestyi sekä Australiassa että Yhdysvalloissa. Tämän jälkeen yhtye on tasaiseen tahtiin julkaissut albumeita, musiikkivideoita ja kirjoja.
Yhtyeen läpimurto tuli vuonna 1992, kun heidän albuminsa Not Ashamed oli ehdolla Grammy-palkinnon saajaksi Gospel Rock -kategoriassa. Yhtye on saanut sen jälkeen vielä kolme Grammy-ehdokkuutta albumeillaan Going Public (1994), Take Me to Your Leader (1996) ja Adoration: The Worship Album (2003).
Newsboys on selviytynyt huomattavan monesta jäsenvaihdosta hajoamatta. Merkittävin lähtö tapahtui, kun yhtyeen siihenastinen solisti John James lähti yhtyeestä vuonna 1997. Hänet korvasi yhtyeen rumpalina ja kakkoslaulajana toiminut Peter Furler, joka lähti yhtyeestä vuonna 2009. Nykyään Newsboysissa ei ole enää jäljellä yhtään alkuperäistä jäsentä. Newsboys on yksi pisimpään aktiivisena olleista kristillisistä rock/pop-yhtyeistä.