Po wydaniu w grudniu 2003 roku płyt z nagranym materiałem, zatytułowanym Full Diesel, zespół zaczął koncertować i rozprowadzać płyty w celu zainteresowania słuchaczy. Skuteczna promocja dema doprowadziła do współpracy z fińskim producentem gier komputerowych, Bugbear Entertainment, który umieścił dwa utwory z dema zespołu: „No Man’s Land” i „King of Defeat” na ścieżce dźwiękowej gry FlatOut. Podczas kilku pierwszych koncertów zespołu rolę basisty pełnił Eric Lunden z grupy The Mind of Doll, po czym zastąpił go Kim Blomberg. Po odejściu Blomberga w maju 2004 roku zespół zaproponował stanowisko basisty Jamo Valtonenowi, który przyjął ofertę.
W sierpniu 2004 roku Full Diesel rozpoczął nagrywanie nowego materiału, który ukazał się 25 stycznia 2005 roku w postaci minialbumu zatytułowanego Gun-Shy. Materiał ten zebrał dobre recenzje, wygrał również konkurs stacji radiowej (YleX), a dzięki głosom słuchaczy stacji pozostał przez dodatkowy tydzień na jej liście przebojów. W sierpniu 2006 roku ukazało się natomiast drugi minialbum zespołu, noszący tytuł 187.