Wenige Wochen nach dem deutschen Überfall auf die Sowjetunion 1941 begann auf Befehl des Reichsführers der Schutzstaffel (SS) und "Chefs der deutschen Polizei", Heinrich Himmler, der Bau eines "Kriegsgefangenenlagers der Waffen-SS" in dem Lubliner Vorort Majdan Tatarski. Dort sollte die zentrale Militärverpflegungsbasis für die im Osten geplanten SS-Dienststellen und -Wirtschaftsunternehmen entstehen. Für den Bau und Betrieb der Wirtschaftsunternehmen beschloss die SS, die erwarteten sowjetischen Kriegsgefangenen als Arbeitskräfte einzusetzen. Die Wehrmacht schien jedoch nicht in der Lage oder willens zu sein, die dringend benötigten Arbeitskräfte in ihren Kriegsgefangenenlagern am Leben zu halten. Der Großteil der Gefangenen kam dort aufgrund der katastrophalen Bedingungen ums Leben, so dass nur wenige Rotarmisten nach Majdanek überstellt wurden. Zudem konnten dringend benötigte Baumaterialien für das Lager in Lublin infolge kriegsbedingt stark beschränkter Transportwege nicht geliefert werden. So scheiterte das Vorhaben Heinrich Himmlers, das Kriegsgefangenenlager weiter auszubauen, und Majdanek blieb ein Provisorium.
Nach einem Befehl Himmlers vom 19. Juli 1942, der die Räumung der Ghettos im Generalgouvernement bis Ende des Jahrs vorschrieb, wies die SS zahlreiche Juden aus der Region Lublin sowie Bewohner der Warschauer und Bialystoker Ghettos in das Lager ein. Nur wenige Juden sollten, in Zwangsarbeiterlagern der Rüstungsindustrie zusammengefasst, zunächst am Leben gelassen werden. Darüber hinaus wurden slowakische, tschechische und slowenische Juden sowie Polen nach Majdanek deportiert.
Im Februar 1943 wurde Majdanek in "Konzentrationslager Lublin" für polnische politische Häftlinge und Juden umbenannt und entwickelte sich darüber hinaus zur Sammelstelle für die im Zuge der Kolonisierungs- und Repressionsaktionen deportierte Landbevölkerung aus Polen und der Sowjetunion. Die KZ-Insassen wurden hauptsächlich in den "Deutschen Ausrüstungswerken" (DAW) und den SS-Bekleidungswerken zur Verarbeitung des Eigentums der ermordeten Juden für den Frontbedarf eingesetzt. Häftlinge, deren Arbeitskraft die SS nicht oder nicht mehr nutzen konnte, ermordete sie ab Oktober 1942 in einer neu errichteten Gaskammer. Zur Verbrennung der Leichen ließ die Lagerverwaltung im September 1943 ein neues Krematorium mit fünf Brennöfen bauen.
Nach Aufständen in den Vernichtungslagern Sobibor und Treblinka erschoss die SS in Majdanek aus Sorge vor weiteren Unruhen im November 1943 rund 17.000 Juden innerhalb weniger Stunden im Rahmen der "Aktion Erntefest". Weitere unzählige KZ-Insassen starben an Hunger, Krankheiten und den harten Arbeitsbedingungen.
Als sich die Rote Armee im Frühjahr 1944 im Vormarsch auf das Lager befand, wurden etappenweise mehrere Hundert Häftlinge nach Auschwitz überstellt und die anderen auf einen "Todesmarsch" geschickt. Um keine Spuren ihrer Verbrechen zu hinterlassen, vernichtete die Lagerverwaltung alle wichtigen Dokumente und setzte das Lager in Brand. Die Gaskammern und ein Großteil der Gefangenenbaracken konnten aus Zeitmangel nicht mehr zerstört werden. Am 23. Juli 1944 wurde Majdanek als erstes nationalsozialistisches Konzentrations- und Vernichtungslager von den Sowjets befreit. Mindestens 78.000 Menschen, darunter bis zu 60.000 Juden, sind im KZ Lublin ums Leben gekommen.
Im November 1944 wurde auf dem Gelände des ehemaligen Konzentrations- und Vernichtungslagers das "Staatliche Museum Majdanek" eingerichtet, das heute eine Dauerausstellung zur Lagergeschichte sowie ein Archiv beherbergt.