Tato melodic power metalová skupina byla založena Thomasem Youngbloodem a Richardem Warnerem ve městě Tampa ve státu Florida roku 1991.

Jejich začátek se však dá datovat od roku 1994, kdy podepsali smlouvu s Noise Records a hned přístí rok, 1995, vydali své debutové album Eternity. Další album, Dominion, vydávají roku 1997. Později tohoto roku kapelu opouští bubeník a jeden ze zakládajících členů skupiny Richard Warner spolu s frontmanem Markem Vanderbiltem. Ti jsou posléze nahrazeni Caseyem Grillem(Bicí) a Royem Khanem(Zpěv), který studoval operní zpěv a měl za sebou již angažmá v power-progressive metalové skupině Conception. V tomto novém složení vydávají v roce 1998 své třetí album Siege Perilious. Ještě ten rok se vydávají na turné po Evropě, ze kterého se po dvanácti měsících vracejí a nahrávají další, čtvrté, album The Fourth Legacy.

Léto 2000 přináší turné New Allegiance Tour začínající v Německu pokračující Rakouskem, Švýcarskem, Nizozemím, Belgií, Itálií, Řeckem a končící Španělskem, během něhož se nahrálo první živé album The Expedition. Jen pár měsíců na to, představil Kamelot své, v pořadí páté, album Karma.

Jejich šesté album, Epica, vychází roku 2003. Pro jeho podporu vyráží kapela na další turné po Evropě a navíc i Japonsku, na pomoc si berou německou skupinu At Vance. Obě alba, Epica i nově vydané album The Black Halo, které bylo vydáno v roce 2005, jsou založena na díle Faust od Johanna Wolfganga von Goetha, které vypráví o muži, co prodal svou duši ďáblu. Aby podpořili album Black Halo, vydali se znovu na turné po Evropě a Japonsku. Na první části Black Halo World Tour 2005 v Evropě, hráli spolu s holandskou skupinou Epica a finským projektem Tima Kotipelta, Kotipelto. V Japonsku jim pomohli němečtí Silent Force. Vystupovali také na německých festivalech Bang Your Head!!! a Graspop Metal Meeting.

Ve stejném roce natočili klipy k písním The Haunting (Somewhere in Time) a March Of Mephisto, obě z alba The Black Halo pod vedením režiséra Patrica Ullaeuse. 5.října 2005 přijali jako pátého oficiálního člena Olivera Palotaiho, který zastoupil post klávesisty a případně i kytaristy.

V druhé části Black Halo Tour 2005 se vydali po jižní a severní Americe(USA, Kanada, Brazílie).

30.října 2006 vydávají DVD One Cold Winter's Night, které bylo pořízeno Patricem Ullaeusem v Rockefeller Music Hall v Norském Oslu. Krátce poté je vydán koncert i na cd. Na tomto koncertu vypomáhá i klávesista Oliver Palotai.

V roce 2007 vychází nové album s názvem Ghost Opera s Oliverem už jako řádným členem kapely.

V lednu 2009 Kamelot začal pracovat na svém devátém albu. Bylo řečeno, že skupina zkoumala "nové zvuky" a že témata na novém albu budou různorodá. Začátkem roku 2010 zveřejnil Kamelot tituly tří písní z nadcházejícího alba na svých oficiálních stránkách: "The Great Pandemonium", "Hunter's Season" a "Thespian Drama". Oznámili také, že se objeví hostující hudebníci: Simone Simons (zpěvačka pro baladu "House on a Hill" a titulní skladbu alba) a později Gus G z řecké power metalové skupiny Firewind. Dne 25. března 2010 zahájili turné "Pandemonium over Europe", které skončilo 26. dubna 2010. Kapela poté odhalila titul svého devátého studiového alba "Poetry for the Poisoned". To bylo vydáno v earMUSIC v Evropě 10. září 2010 a v KMG v Severní Americe 14. září 2010. Video klip "The Great Pandemonium" režíroval Owe Lingvall a byl vydán 1. září 2010. Poetry for the Poisoned vstoupil do USA Billboard 200 žebříčku na místě 74. Během léta roku 2010 hráli na festivalech Wacken Open Air, Rock am Ring, Tuska Open Air Festival. Poslední z festivalového turné byl srpnový Sziget Festival.

Dne 6. září 2010 skupina oznámila, že se Khan vážně zranil při zkouškách na nadcházející severoamericé turné, jen několik dní před plánovaným začátkem a vrátil se do Norska. Zatímco bylo zpočátku hlášeno, že skupina bude pokračovat v turné s norským zpěvákem Michaelem Eriksenem z Cirkus Maximus, skupina později oznámila, že odjede turné s Khanem, ačkoli jedna show byla uvedena s Eriksenem na ProgPower USA XI festival v Atlantě. Nicméně dne 16. prosince kvůli Khanově přetrvávající nemoci bylo oznámeno, že Fabio Lione z Rapsody of Fire nahradí Khana na zbývající a přeplánované termíny na turné Pandemonium v Latinské Americe, Evropě a Severní Americe v roce 2011. Další hosté se objevili na vybraných koncertech, jako například Simone Simons zpívá "The Haunting" a "Don't You Cry", Tommy Karevik "Center of the Universe", "EdenEcho" a "The Human Stain", Snowy Shaw jako Mephisto v "March of Mephisto", Alissa White-Gluz také jako Mephisto v "March of Mephisto" a Atle Pettersen v písni "Karma". 15. dubna 2011 skupina vydala "Poetry for the Poisoned & Live from Wacken – Limited Tour Edition", obsahující zvuky z poslední nahrané přehlídky Khana s kapelou.

Po období nejistoty vydali Roy Khan a Kamelot 21. dubna a 22. dubna 2011 samostatná prohlášení oznamující odchod Roye Khana z kapely.

Kamelot 22. června představil Tommyho Karevika jako svého nového oficiálního zpěváka. Karevik se předtím objevil jako jeden z hostujících zpěváků na turné Pandemonium World Tour 2011.

Kamelot se vrátil k německé značce SPV GmbH, aby vydal své desáté album (první s Karevikem), který byl odhalen jako Silverthorn v červenci spolu s datem vydání 26. října 2012. Hudební video bylo vydáno pro první singl z Silverthorn , "Sacrimony (Angel of Afterlife)". Kapela se spojila s Nightwish na severoamerickém turné jako zvláštní host během září a října 2012, v období před vydáním Silverthorn, spolu s hostujícími zpěváky Elize Ryd a Alissou White-Gluz. Po severoamerickém turné se Kamelot v listopadu 2012 vydal na evropské turné s podporou Xandria, Triosphere a Blackguard. Silverthorn byl přivítán s pozitivními recenzemi a skupina se opět umístila na první desítce na americkém Billboard Charts. Kapela také navštívila se Silverthornem nové země včetně Austrálie, Koreje a Tchaj-wanu. Cyklus turné pro album skončil zájezdem do Evropy, Severní Ameriky a konečně do Jižní Ameriky 2014. Během interview v roce 2013 Youngblood uvedl, že nový zpěvák Karevik překonal očekávání. V dalším rozhovoru 3. října Youngblood uvedl, že Kamelot začne nahrávat další album v polovině roku 2014.

V roce 2014 si skupina dala volno od turné a soustředila se na práci na dalším albu. Odehráli pouze dva festivaly v Evropě, Sweden Rock Festival a Masters of Rock Festival a dvě klubová vystoupení, jednu v Trondheimu a jednu v Haarlem. V Haarlem hráli speciální akustickou sadu, která zahrnovala živou premiéru Welcome Home a akustickou premiéru Karmy.

23. února 2015 bylo oznámeno, že nové album Kamelot bude nazváno Haven. Bylo vydáno 5. května 2015. Alissa White-Gluz, Troy Donockley a Charlotte Wessels se objevily jako hosté na albu.

Album bylo dobře přijato kritiky a fanoušky a vedly k tomu, že vstoupilo na US Billboard Charts na místě 75 a Billboard Hard Rock Charts na místě 1. Krátce před vydáním alba Kamelot začal nové světové turné na propagaci alba, Severní Amerika s Dragonforce jako zvláštním hostem. Během léta hráli na Masters of Rock, Kavárna Rock Fest a Rock by River Festival. Později v roce se kapela vrátila do Evropy s podporou Kobra and the Lotus a Gus G. Mezi jejich koncerty v Miláně a Štrasburku se přes víkend přesunuli do Japonska na festival Loud Park. Roku 2015 byla uzavřena druhá etapa amerického turné, znovu s Dragonforce. Kamelot v roce 2016 pokračuje na živých koncertech na podporu Havenu a přináší je opět do Evropy, ale také do Japonska a Jižní Ameriky. Kamelot vydal tři hudební videa pro Haven: Insomnia, Liar Liar (Wasteland Monarchy) a My Therapy.