Grubun vokalisti Lacey Mosley, Teksas eyaletinde 6 çocuklu fakir bir ailede dünyaya geldi. Zor bir çocukluk dönemi geçiren Lacey o günleri, "Uyuşturucuyu ilk kez denediğimde 10 yaşındaydım. Bunun yanlış olduğuna dair düşüncelerim vardı. Bir şekilde bunun yanlış olduğunu hissediyordum. Uyuşturucu kullandığımı okuldaki arkadaşlarıma söylemedim. 13 yaşıma geldiğimdeyse, benim gibi madde kullanan insanlarla tanıştım ve olan oldu. Gittikçe dibe batmıştım. Kim olduğumu anlamaya çalışıyordum. Ailemi ya da evde yaşananları unutturan ne varsa bana iyi geliyordu" sözleriyle anlatıyor.

14 yaşında bir bas gitar edinen Lacey, Green Day ve Nirvana şarkıları çalmaya başladı. 16 yaşına geldiğinde annesiyle arasında yaşanan kavganın boyutu öyle bir hal almıştı ki, Lacey evi terkedip Mississippi'ye gitmek, orada büyük annesiyle yaşamak zorunda kaldı. Gulfport lisesine devam ederken müzikle uğraşmayı kesmeyen Lacey, okuldaki bir grubun bas gitarist aradığını duydu. Denemelerden sonra gruba girmeyi başardı. Bu grupta bas çalmakla yetinmedi. Bir süre sonra şarkı söylemeye, gitar çalmaya ve şarkı yazmaya başladı. Lacey'nin söyleyecek çok fazla şeyi vardı. Ortaya çıkan şey çoğu zaman sonu ölüm ve ateizme varan karanlık imalar taşıyordu. Bu durum, grup üyeleri arasında gerginliğe yol açtı; çünkü kimse bu işi Lacey kadar ciddiye almıyordu. Annesinin evindeki fakirlik dolu yaşamının ardından büyük annesinin zenginlik ve ihtişamı barındıran evine adım atmış, bu sayede iki ucu da ruhuna sindirmişti. Biraz parası olsun isterken kendisini zenginlik içinde bulunca "bu muymuş?, bu kadar mı?" diye düşündü. "Hayatın bana verebilecekleri bu kadar mı yani? Eğer öyleyse bu durumdan memnun değilim", diye düşündü. 16 yaşında kendisini her şeyin sonuna gelmiş hissediyor, intihar etmek istiyordu. Bir gün geçirdiği sinir krizinin ardından saçını kesti. Buna sinirlenip deliye dönen büyük annesi onu zorla kiliseye götürmeye başladı. Başta oraya büyük annesini susturmak için giden Lacey, papaz yardımcısıyla arasında geçen bir konuşmadan sonra ruhuna bir kamçı yedi. Lacey, o günden sonra yaşamına inançlı bir insan olarak devam etti.

Kısa süren bir evliliğin ardından Teksas'a geri dönen Lacey, orada davulcu James Culpepper ile tanıştı. James, Lacey'nin şarkılarından etkilendi ve parçalara uygun ritmler üzerinde çalışmaya başladı. İşte konumuz olan Teksaslı alternatif metal grubu Flyleaf, 2000 senesinde Lacey Mosley ve James Culpepper tarafından kuruldu. Birlikte müzik yapmaktan o kadar zevk alıyorlardı ki, Lacey için müzik yapmak hayatının en büyük amacı olmuştu. Jared Hartmann, Sameer Bhattacharya ve Pat Seals'in de katılımıyla son halini alan topluluk, "Passerby" ismiyle müzik piyasasına giriş yaptı. Runt Entertainment çatısı altında 3 ep yayımlayıp 100'den fazla konser veren Passerby üyeleri, RCA'nın daveti üzerine gittikleri New York'ta sergiledikleri performansa gizlice çağrılan Octone Records'dan albüm teklifi aldılar. 2004 yılında Seattle' gidip Rick Parasher'la birlikte bir ep kaydeden müzisyenler; Breaking Benjamin, Staind ve 3 Doors Down ile birlikte turlayarak kendi isimlerini taşıyan bu ep'yi izleyicilere tanıttılar. Turne sonrası piyasaya sürülen ep'yi grubun ilk resmi single'ı "Breathe Today" ve ona çekilen video klip izledi.

2005 senesinde Howard Benson'la ilk stüdyo albümünü kaydeden grup, bu albümü "Flyleaf" ismiyle piyasaya sürdü. Albümden ilk single'lar "I'm so Sick", "Fully Alive" ve "All Around Me" parçalarına seçildi. 2006'da plak şirketini değiştiren grup, Family Values Turnesi'nde performans sergiledi. 2006'da Disturbed, Stone Sour ve Nonpoint gruplarıyla Music As A Weapond III Tour'da yer alan Flyleaf, sadece bu turnede satışa sunulmak üzere "Music As A Weapon" ismini taşıyan özel bir ep hazırladı. "Much Like Falling", "Justice And Mercy" ve "Christmas Song" gibi daha önceden yayımlanmamış şarkıların yanında "Fully Alive"ın akustik versiyonunu da içeren bu ep'nin gelirlerinin bir kısmı dini bir kuruluş olan "World Vision"a bağışlandı.

2007'de Three Days Grace ile birlikte Avustralya turnesine çıkan grup; Stone Sour ve Forever Never ile birlikte Avrupa'da konserler verdi. Aynı sene vizyona giren Live Free or Die Hard filminde "I'm So Sick" parçasının klip görüntülerine az da olsa yer verildi. Parçanın remix'i ise Resident Evil: Extinction'da yer aldı. 2007'de ilk albümün yeni versiyonunu ve "Much Like Falling" isimli ep'yi dijital olarak satışa çıkaran topluluk, ep'de "Much Like Falling", "Tina" ve "Justice and Mercy" parçalarının yanı sıra "Supernatural"ın akustik versiyonuna yer verdi.

2008'de Bitch We Have a Problem turnesinde Korn'a eşlik eden Flyleaf, 26 Nisan 2008'de "Sorrow" single'ını piyasaya sürdü. Daha sonra Seether'la birlikte turneye çıktı; fakat Lacey'nin ses tellerindeki problem nedeniyle 5 konser iptal edildi. İyileşmenin ardından konserlerine devam eden grup, yeni albüm için de çalışmalara başladı.