For My Pain... sai alkunsa Eternal Tears of Sorrow -yhtyeen laulaja ja basisti Altti Veteläisen ja rumpali Petri Sankalan sivuprojektina vuonna 1999. Kaksikko pyysi mukaan vanhoja ystäviään Nightwish-yhtyeen Tuomas Holopaista ja Embraze-yhtyeen laulajaa ja myös Charonissa vaikuttavaa Lauri Tuohimaata, jotka kiinnostuivat ajatuksesta, mutta kaikki neljä olivat lopulta liian kiireisiä muiden hankkeidensa parissa ja idea päätettiin hyllyttää toistaiseksi. Kahden vuoden päästä vuonna 2001 asia nostettiin uudestaan esiin sekä Eternal Tears of Sorrow'n ja Nightwishin ollessa tauolla. Kokoonpano täydentyi EToS:n entisellä kitaristilla Olli-Pekka Törröllä ja Reflexionin laulajalla Juha Kylmäsellä. Yhtyeen ensimmäinen ja toistaiseksi ainoa albumi, Fallen, nauhoitettiin Kemin Tico Tico -studiolla keväällä 2001 ja julkaistiin lopulta Spinefarm Recordsin kautta 31. maaliskuuta 2003. Vuonna 2004 julkaistiin single Killing Romance, joka sisälsi myös cover-version Yö-yhtyeen kappaleesta Joutsenlaulu.