2004–2010: Anfänge und Debütalbum

Paper Route wurde 2004 von Chad Howat gegründet. Aufgrund seiner Schlafstörungen blieb dieser nachts oft lange wach und schrieb erste Musikstücke. Die Band wurde später durch seine Freunde J.T. Daly und Andy Smith ergänzt, mit denen Howat schon seit der Collegezeit in Greenville musizierte. Im Jahr 2006 begannen sie, erste Platten zu veröffentlichen, darunter die am 29. August 2006 erschienene, selbstbetitelte EP Paper Route und das Weihnachtsalbum A Thrill of Hope. Letztgenanntes erschien über das Major-Label Universal Music, bei dem die Band bis 2010 unter Vertrag stand. Am 8. Juli 2008 folgte eine weitere EP mit dem Titel Are We All Forgotten. Das Debütalbum Abscence erschien am 28. April 2009. Es ist die erste Veröffentlichung, auf der der Schlagzeuger Gavin McDonald zu hören ist, der der Band nur kurz zuvor offiziell beigetreten war. Zu Weihnachten desselben Jahres wurde außerdem Thank God the Year Is Finally Over veröffentlicht. Daraufhin tourte die Band eine Zeit lang gemeinsam mit Paramore und Phantom Planet.

2011–2013: Zweites Album und Charterfolg

Nach der Veröffentlichung der mehrere Remixe enthaltenden EP Additions wurde es erstmal still um die Band. Erst als bekanntgegeben wurde, dass Gitarrist und langjähriges Mitglied Andy Smith die Band Anfang 2012 verlassen hat, rückte man wieder ein wenig in den Fokus der Medien. Am 11. September 2012 wurde von der dementsprechend nunmehr dreiköpfigen Formation das zweite Studioalbum The Peace of Wild Things über das Label Tree of Hearts veröffentlicht. Es enthielt zehn Lieder und stieg auf Platz 164 der US-amerikanischen Billboard 200 ein, wo es sich eine Woche hielt. Es belegte außerdem den 34. Platz der neuseeländischen Albumcharts. Im Anschluss begleiteten sie unter anderem die Imagine Dragons auf Tour.

Seit 2014: Drittes Album und Pause

Nachdem auch Gavin McDonald die Band verlassen hatte, musste die inzwischen auf ein Duo geschrumpfte Rockband einige Auftritte absagen und weitere Single- bzw. Tonträgerveröffentlichungen vorerst auf Eis legen. Erst als ihnen der Gitarrist Nick Aranda beitrat, konnten sie mit den Arbeiten an einem neuen Album fortfahren. Dieses erschien am 23. September 2016 über Kemosabe Records, ein Sublabel von Sony Music, unter dem Namen Real Emotion. Es wurde – besonders durch die Fachpresse – überwiegend positiv rezipiert, wenngleich es nicht an die großen kommerziellen Erfolge des vorangehenden Albums anknüpfen konnte. Für den Soundtrack des Videospiels FIFA 17 wurde die auf Real Emotion enthaltene Single Chariots verwendet.

Anfang 2019 gaben die Mitglieder über Twitter bekannt, dass sie als Musikgruppe vorerst auf unbestimmte Zeit pausieren. Insbesondere Sänger J.T. Daly widmet sich seitdem anderen Band-Projekten, wie beispielsweise 2020 mit The Voodoo Children.