Beloved se formó en el otoño de 1999. Todos los miembros originales asistieron a la escuela secundaria East Forsyth en Kernersville, NC, de 1996 a 2000. Tocaron en espectáculos locales en las áreas circundantes de Kernersville, donde crecieron en popularidad casi de inmediato. En 2000, lanzaron de forma independiente su primer álbum, ...And So It Goes . La banda realizó una gira por el país con bandas como Underoath , Luti-Kriss / Norma Jean y Cool Hand Luke , incluida una actuación en el Cornerstone Festival .
En la primavera de 2001, llamaron la atención del sello Vindicated Records, que lanzó su siguiente lanzamiento, The Running , ese mismo año. Durante este tiempo, la banda también lanzó un prelanzamiento en línea limitado para The Running que incluía versiones preliminares de estudio de las pistas "The Blue Period" e "Into Your Arms". La segunda pista no se incluyó en el lanzamiento de Vindicated Records y no se lanzó comercialmente hasta el segundo relanzamiento de Solid State Records .
En 2002, la banda estaba en proceso de firmar con Takehold Records . [2] Sin embargo, el propietario de Takehold Records, Chad Johnson, también estaba negociando la venta del sello a Tooth & Nail Records en ese momento.
Finalmente, Takehold se vendió a Tooth & Nail y Beloved firmó con la división Solid State Records de Tooth & Nail. Solid State relanzó su EP, The Running , para su presentación en Cornerstone en el verano de 2002. [3]
A fines de 2002, mientras estaban de gira con Luti-Kriss / Norma Jean , ambas bandas grabaron espontáneamente un EP dividido que constaba de dos canciones de cada banda. Este "lanzamiento" fue apodado One Night Split y fue increíblemente limitado. Solo se produjeron unas pocas copias en formato CD-R, y se entregaron a los afortunados fanáticos en las paradas posteriores de la gira después de su grabación. Las dos pistas de Luti-Kriss fueron renombradas más tarde y llegaron al primer lanzamiento del grupo como Norma Jean , Bless the Martyr y Kiss the Child ; mientras que la mitad de Beloved incluía el himno "Death to Traitors", que se lanzó en su álbum de larga duración Failure On ., y una pista titulada "Westward Shining" que permanece inédita.
Al año siguiente, la banda ingresó al estudio con el productor GG Garth para grabar su siguiente álbum de larga duración, Failure On . [4] La banda apoyó el álbum con una extensa gira y otro relanzamiento de The Running con el bonus track previamente grabado "Into Your Arms" en 2004.