Работа над альбомом началась в феврале 2012 года[13]. Первым синглом стала одноимённая композиция «New Horizons»; сингл вышел на iTunes 21 августа[11]. Басист группы, Пэт Силс, назвал песню «одной из лучших» в творчестве группы и заявил о том, что она повествует об ожидании неизвестности будущего с надеждой[11]. Видеоклип «New Horizons» вышел 4 сентября 2012 года[16]. Вторым синглом, вышедшим через месяц, стала песня «Call You Out»[17].
↑James Christopher Monger.New Horizons - Flyleaf (неопр.). Allmusic (30 октября 2012). Дата обращения: 4 ноября 2012. Архивировано из оригинала 29 декабря 2012 года.
↑Luke Spencer.New Horizons from Flyleaf (неопр.). Alt Rock Live (30 октября 2012). Дата обращения: 5 ноября 2012. Архивировано из оригинала 29 декабря 2012 года.
↑Tyler Hess.Flyleaf – “New Horizons” (Review) (неопр.). Christian Music Zine (5 ноября 2012). Дата обращения: 8 ноября 2012. Архивировано из оригинала 29 декабря 2012 года.
↑Flyleaf, "New Horizons" Review (неопр.). Jesusfreakhideout.com (29 октября 2012). Дата обращения: 4 ноября 2012. Архивировано из оригинала 29 декабря 2012 года.
↑Paige Camisasca.Review: Flyleaf – New Horizons (неопр.). Revolver (25 октября 2012). Дата обращения: 4 ноября 2012. Архивировано из оригинала 29 декабря 2012 года.