Stone Wings [formerly Elysium], now Sydney's longest-surviving and most well-known doom act, was formed in September 1994 by Stuart Prickett [vocals/guitar] and Beau Dyer [drums] through a mutual love of doom metal. They were soon joined by Robert Vickery [bass/vocals] and played their first live gig in November 1994. The next few months were spent writing new songs and rehearsing, and in February 1995 they were joined by Hamish Gould [keyboards], but in the same month Beau decided to leave to concentrate on his other band, Across The Scarlet Moat. A new drummer was quickly found – Roy Fratini – and with this lineup Elysium started to gig regularly. In August 1995 they released a rehearsal promo which was spread through the underground. Then in October 1995, the four-piece recorded their debut demo, consisting of six songs of epic death/doom, which was released in November 1995; the band gigged constantly in support of this release. In January 1996, the demo was re-released through Warhead Records and sold strongly throughout the underground scene. The demo garnered mostly good reviews and gained the band a strong following in underground circles. All went well for a period but problems arose and things went downhill in a personal sense. In June 1996 the band split in two directions, leaving only Stuart and Hamish to continue things; a move which turned out for the best.

The day after the split Beau rejoined, this time as bassist, and the band gained a fulltime vocalist: Jamie Marsh [Lord Kaos]. The band had trouble finding a suitable drummer and second guitarist; Elysium continued to write new material, however, and eventually in August 1996 a suitable new drummer, Lachlan Donaldson, was found and the core of the band was stable once again. After many rehearsal sessions a second demo was recorded, entitled Shrouded in the Veils of Dawn in November 96. This demo became available in June 1997. In July 1997 a new guitarist, Andrew Habib, was found to complete the lineup and in December 1997 Lachlan was replaced by Neil Dyer on drums.

During this time the debut album Dreamscapes was recorded but the release was delayed greatly due to the collapse of Warhead Records, leaving the band without a deal until De Profundis Records expressed interest; the CD was finally released in March 2001, and also gained good reviews in many fanzines. A promo cassette, Promo 94-98, was released in mid-1998 featuring old and new material, as well as some live bootleg and rehearsal tracks. A three-song promo was also released in mid-1999 just in time for the band's first interstate show in Adelaide.

In September 2002 the band changed their name from Elysium to Stone Wings, due to the increasing number of 'Elysiums' appearing in the metal scene; the band wanted to avoid causing further confusion and also wanted a more original name that wasn't likely to be used by anyone else.

Stone Wings have finished the recording of their second full-length album, Bird of Stone Wings, which will be released towards the end of 2003, featuring seven tracks of heavy doom metal with a running time of sixty-nine minutes. A promo CD will be released in June 2003 featuring two tracks from this album and some older, rare material.