Według legendy nazwa miasta pochodzi od nazwiska bogatego kupca Keidangena, przybyłego tu znad morza, aby założyć wioskę rybacką. Pierwsza wzmianka o mieście pochodzi z 1372 r. z kroniki inflanckiej Hermana Wartberga. W XV w. Kiejdany stały się centrum handlowym, do którego przybywali zagraniczni kupcy i rzemieślnicy. W ciągu 300 lat miasto należało do rodziny Radziwiłłów. W XVII w.było w nim centrum protestantyzmu, powstało gimnazjum protestanckie, budowano murowane domy, brukowano ulice. Ważna droga, zwana żwirówką, z rozkazu Janusza Radziwiłła była zadbana i doglądana, a każdy, wjeżdżający do miasta, miał przywieźć kamień do brukowania ulic.
Na początku XVII w. pojawili się tu Szkoci i Kiejdany stały się ważnym centrum ich społeczności.
Żydzi również byli ważnym elementem miasta. Zajmowali się rzemiosłem, sprzedawali alkohol, byli złotnikami, blacharzami, szewcami, furmanami,kuśnierzami, krawcami, mieli karczmy, pożyczali pieniądze. Żydom „ uczciwym i dobrze wychowanym“ można było mieszkać przy Starym Rynku. Do połowy XX wieku Żydzi tworzyli więcej niż połowę mieszkańców. To Żydzi przywieźli do Kiejdan ogórki i rozpowszechnili te warzywa. A po powstaniu kolei swoje ogórki sprzedawali nie tylko na Litwie, ale na Łotwie. Obecnie co roku są organizowane jedyne na Litwie fiesty ogórkowe.
W 1941 r. żydowska część miasta stała się gettem. W czasach drugiej wojny światowej rozpoczął się holokaust. Rozstrzelano 2410 Żydów. Prowadzeni na stracenie bili się w piersi i mówili: „Ich bin kiejdaner“.
W 1811 r. Kiejdany stały się własnością hrabiów Czapskich. W 1844 r. Marian Czapski na prawym brzegu rzeczki Datnówki zbudował piękny pałac, przy którym była wspaniała baszta, oranżeria i park. Powstania 1831 i 1863 r. dotknęły boleśnie Kiejdany i okolice. W 1831 r. zamknięto klasztor, który stał się wojskowymi koszarami. Po 1863 r. pałac Czapskich skonfiskowano, Marian Czapski za udział w powstaniu zesłany został na Syberię. Pałac oddano generałowi armii rosyjskiej Edwardowi Totlebenowi. On pałac przebudował, powiększył park, ustawił w nim wiele rzeźb i minaret. W 1944 r. Niemcy pałac wysadzili w powietrze.
