Adastreia began in July 2004 when a previous musical project involving Del, Matt & Westley disbanded. After initially forming as a four-piece with Alexandra on vocals and keyboards it was decided that a dedicated keyboard player was needed to free Alexandra up for her vocal duties. Hilary joined the band that October, adding her considerable talents to Adastreia enabling them to concentrate on working on material for the Emersi EP which was recorded in June 2005 at the Adelaide Studios, Essex. Engineered by Grant Matthews, the demo contains the tracks 'Cold Moon', 'Emersi', '...Of Your Last Regrets' and 'Aislinn'. The debut EP kicked up a storm with "Cold Moon" appearing on Terrorizer's 2005 Unsigned CD on the cover and a few months later inside the magazine Adastreia ranked as joint 4th best unsigned band with Season's End in the end of year reader's poll.

Dave joined Adastreia as 2005 became 2006 as a second guitarist to expand the band's sound. While recording the 'Masked' single in March 2006 the band performed a show with friends Forever Never & Season's End at the popular Underworld venue in London's Camden Town, a stage that Adastreia would become familiar with. The 'Masked' single was released that April shortly before being invited to support Epica at the Underworld which served to raise the popularity of Adastreia further. Over the course of 2006 Adastreia continued to play shows in and around venues in London with Season's End, NFD, The Deathstars, To-Mera & Xandria. The band also played a show at the UK's Bulldog Bash festival and wrapped up 2006 with a small UK tour with Edenbridge including a date at the well-known Bradford Rio.

The beginning of 2007 was a fairly quiet period for Adastreia with time being split between writing new material, rehearsals and external commitments. The band performed a handful of London and local shows earning good reviews including a local rock festival and two more Underworld shows with To-Mera, Octavia Sperati and in June Adastreia entered the Essex-based Shack Studios to record their debut album. In September the band again supported Xandria at the Underworld which unfortunately marked the departure of Hilary from the band. Early November saw the completion of production and the release of 'That Which Lies Within', an accumulation of the band's work since 'Masked' spread over forty-five minutes and seven tracks once again engineered by Grant Matthews and produced by Adastreia and John Biscomb from fellow Essex band Dead Beyond Buried. In March 2008 Josiah Lutton joined the band as replacement for Hilary and now the band plan to return to playing shows and promote the release of That Which Lies Within.