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.