Perth "True Scottish pirate Metal" band ALESTORM is rooted in the 2004 founded BATTLEHEART. This incarnation of the group, created by guitarist Gavin Harper and singer Christopher Bowes. Following issue of an April 2006 EP, which included a cover version of KORPIKLAANI's 'Journey Man', the band inducted bassist Dani Evans and drummer Doug Swierczek. In this formation the group conducted its debut live performance at the Balcony Bar in Dundee on 30th June. BATTLEHEART's second EP, 'Terror On The High Seas', arrived in October.

Dani Evans briefly switched instrument to rhythm guitar with Jason Heeny brought in on bass, However, within a few months Heeny was to opt out and Evans returned to his former position. In early 2007 Doug Swierczek departed from the band and was replaced by Ian Wilson of CATHARSIS.

Upon signing with Austrian label Napalm Records in 2007 and switching title to ALESTORM. The debut album, Captain Morgan's Revenge' featuring Micha Wagner of INCUBATOR on session drums and produced by INCUBATOR guitar player Lasse Lammert in Lübeck, was released on 25th January 2008. Chris Mummelthey, also INCUBATOR, supplied backing vocals. The album closed in patriotic with a version of the traditional 'Flower Of Scotland'.

In April 2008 the single 'Heavy Metal Pirates' was released as a digital download. Ian Wilson left Alestorm in June of that year, apparently unable to commit fully to touring, and was temporarily replaced by German Alex Tabisz. Wilson returned to the band in late August, rejoining ALESTORM in time for their show at Ivory Blacks in Glasgow on 29th August.

In September 2008 guitarist Gavin Harper departed. Tim Shaw, of PREMITHON and FYRDSMAN, was announced as replacement as the group commenced work on the 'Leviathan' EP. European tour dates in October had ALESTORM partnered with Denmark's SVARTSOT and Portugal's GWYDION.

The EP 'Leviathan' was issued in January 2009. That March the band supported SUIDAKRA across North America on the 'Pagan Knights" tour. The album 'Black Sails At Midnight' arrived in May. Limited edition digipack versions featured different artwork and a bonus DVD disc hosting live footage of the band's 'Wacken Open Air' 2008 festival performance.