Kapela s tímto názvem vznikla v roce 1990 na troskách několika \"předvojenských uskupení\". Ze současných členů byli u zrodu kytarista Radek Sady Sádovský a baskytarista Jiří Mráza Zíma. Od roku 1992 vystřídala dva předchozí zpěváky Simona Křtěnová a vtiskla tak kapele charakteristický punc ženského vokálu. V roce 1993 odešel Mráza na mateřskou dovolenou a i na ostatních postech došlo ke střídání stráží.

V době, kdy se ostatní báli jen vyslovit slova \"Heavy Metal\", aby nepropadli u kritiků a jiných odborníků, stáli si Krleš tvrdošíjně na svém a v roce 1996 natočili debutní album \"Stín předtím\" se šesti skladbami. Název i první skladba čerpali z románu Stephena Kinga \"TO\" a kromě poslední hitovky Kráv´n´roll to byla souprava melodického speed metalu. Album vyšlo pouze na kazetách na vlastní náklady kapely a šlo poměrně slušně na odbyt. Krátce po natočení se opět měnila sestava. Vrátil se Mráza, za bicí usedl Jiří Smělík a byl znovu angažován kytarista Radomír Prezident Dudek.

Další změna byla v roce 1998 po výměně Prezidenta za rusko-lotyšsko-českého kytaristu Jiřího Karpjuka. Takto posíleni vyrazili Krlešáci v červnu 1999 do studia, kde natočili desetiskladbový výtvor \"Dejte plamenům co hoří\". Prolíná se tu rychlé tempo předchozí nahrávky s pomalejšími skladbami a hardrockovým tahem na bránu podpořené výrazným vokálem a okořeněný kytarovými výkony \"Lotyšského Blesku\". Album vyšlo na CD i MC u SIA Production. ...Pod stejnou značkou a ve stejné sestavě natočili Krleš v roce 2001 další album \"TO\". Je o něco tvrdší než \"Plameny\", ale opět nechybí melodika a instrumentální preciznost. Na přelomu listopadu a prosince zosnovali Krleš pokus o sblížení českých Heavy Metalových kapel společně s Cruel Barbarian a Salamandrou odehráli osmikoncertní turné po Čechách.

Na jaře 2002 po neshodách s kapelou odchází nečekaně a proti všem dohodám Simona a na post zpěvačky nastoupila Zuzana Martincová. Svůj křest ohněm si odbyla 10. května v Bratislavě po pěti dnech členství v kapele a jedné zkoušce, takže se nemusel vůbec přerušovat harmonogram koncertů.

Kromě vlastních věcí je produkce obohacena i o převzaté kusy od světových Hard a Heavy rockových velikánů. Další deska ( na přání mnoha Fans ) měla být proto sestavena z coververzí s českými texty. Bohužel několik původních autorů nedalo svolení, z projektu sešlo a mraky práce bylo na . . . !

I přes velké koncertní vytížení (během let hráli Krleš i jako předkapela mnoha známých zahraničních metalových skupin) se kapela po třech letech opět dostala do studia a natočila své třetí CD \"Slzy Arkóny\" textově tématicky zaměřené na osud Polabských Slovanů. Jak je u Krleš zvykem, \"Slzy\" jsou opět o něco tvrdší než předchozí \"TO\" a to hlavně po zvukové stránce. Další koncertní zápřah (80 - 100 koncertů ročně) nevydržel Jirka Karpjuk a kapelu po osmi letech na jaře 2006 opouští a na jeho místo nastupuje Libor Daniš. Mezitím už měla kapela roztočené nové CD TIME TO RISE. V létě opouští Krleš z minuty na minutu uprostřed koncertu i Zuzana... Nastalou situaci řeší kapela radikálně - angažuje bubeníka z kapely Scelet (Roman Lenin Zapadlo) a Jirka Smělík nastupuje za mikrofon. Naštěstí tahle dočasná sestava (pro mnohé možná strašná, ale my se vážně bavili) odehrála jen tři koncerty, když se na jednom z nich přihlásila Lucka Roubíčková coby budoucí zpěvačka.

První společné vystoupení bylo o týden později na rockfestu v Dačicích. CD TIME TO RISE bylo tou dobou už připravené k výrobě, ale kapela nebyla spokojená s tím, jak ho Zuzana nazpívala. Proto bylo rozhodnuto celé CD Luckou přezpívat. Práce na CD se tak díky rošádám v kapele protáhlo na celý rok a vyšlo až v prosinci 2006. Je to výběr z posledních tří CD v angličtině. Texty se drží původních českých originálů. V březnu 2008 končí v kapele Libor a na jeho místo nastupuje Sali. V tomhle složení začíná kapela natáčet své čtvrté řadové album Perunovo Requiem, které vyšlo v srpnu 2008.