«Lost in Paradise» була написана Емі Лі, продюсером виступив Нік Рескулінеш[1]. Пісня була записана в студії Blackbird Studio в Нашвіллі, Теннессі в 2011 році. Під час інтерв'ю для MTV News Емі сказала:
Ця пісня змусила нас кричати. Я люблю її. Коли я писала її, це було щось; вона була чиста, вона була тільки для мене. Я думала, що запишу її удома тільки лише граючи на роялі[2].
Спочатку пісня планувалася Емі Лі як бі-сайд до якого небудь синглу, але в підсумку пісня увійшла в альбом. 22 серпня в студії звукозапису було анонсовано п'ять пісень, «Lost in Paradise» була однією з них.Композиція являє собою симфонічну рок-баладу[3][4][5], що оповідає про любов Емі Лі до гурту Evanescence. Лі сказала, що після взяття творчої перерви вона багато часу проводила зі своїм чоловіком, але все одно відчувала себе загубленою[6]. У підсумку вона вирішила написати пісню як вибачення перед своїми шанувальниками за довгу відсутність.