Rufio были сформированы в 2001, когда Jon Berry, их первый басист, был первокурсником в колледже а остальные три участника Scott Sellers, Mike Jimenez, и Clark Domae были в на последнем курсе старшей школы в Rancho Cucamonga. Sellers и Berry были знакомы в течение некоторого времени и их интересы объединяли гитары и игра на них. Sellers и Berry подходили друг другу, в смысле того что у них было очень много общих интересов и они начали играть вместе в различных группах. Через некоторое время пацаны вдвоем приобрели 4-track, чтобы записать то, что они играли. После того, как Sellers и Berry записались, они дали послушать свои записи Mike Jimenez, и предложили ему играть на барабанах вместе с ними. Вскоре присоединился Domae, и стал завершающим звеном в создании группы. Пацаны выбрали название Rufio. Rufio - это лидер Потерянных Мальчиков, из произведения Питер Пэн.
Дебютный альбом Rufio «Perhaps, I Suppose…» был записан и издан в 2001 на лэйбле The Militia Group. Затем группа вернулась в июне 2003 с альбомом MCMLXXXV, который был записан при помощи Nick Rasculinecz. Этот мужчина записывал Foo Fighters и Rancid. Летом 2003 Rufio поехали на Vans Warped в поддержку своего альбома. И третий их альбом, The Comfort of Home, был издан в июле 2005. Турили вместе MxPx и Relient K. В 2007 группа объявила о своем распаде.
Тем не менее группа сыграла несколько концертов в 2008 и 27 декабря 2009 барабанщик Terry Stirling Jr. анонсировал EP «The Loneliest». Так же Rufio заявили что они записывают лонгплей «Anybody Out There», который выпущен 27 июля 2010 с последующим всемирным туром в его поддержку.