HAL koos voor een contract bij de indieplatenmaatschappij Roughtrade, nadat hun door verschillende grote maatschappijen een contract was aangeboden.
In 2004 kwam hun eerste single uit: Worry About the Wind. Deze single werd zeer goed ontvangen door de pers en in de recensies was veelal sprake van de verwachting dat HAL dé band van 2004 zou worden. Het debuutalbum getiteld HAL verscheen in 2005 en werd eveneens zeer goed ontvangen in de pers. Van dit album werden de nummers Play the Hits, What a Lovely Dance en Don't Come Running/I Sat Down (dubbele A-kant) als single uitgebracht. Ook bracht de band een dubbele elpeesingle uit samen met een andere Engelse band: The Magic Numbers. HAL bracht op deze single het nummer Keep Love As Your Golden Rule uit.
Na een korte tournee door Engeland, Ierland, Europa en Japan ging de band in oktober 2005 de studio's weer in.
Prijzen
The Irish Post Best Newcomer Award 2005
European Border Breakers Award 2006, toegekend door de European Commission in Cannes in januari 2006