Con casi cuatro años de producción, "From a Basement on the Hill", fue finalmente publicado el 19 de octubre de 2004 por ANTI- Records (una subsidiaria de Epitaph Records).