민주노동당 창당 움직임은 15대 대선 직후부터 일어났다. 1998년 2월 21일 건설국민승리21은 운영위원회를 열어 “진보 정당 건설을 목표로 하는 정치 조직으로 전환”하기로 결정하였다. 같은 해 5월 20일 민주노총도 “건설국민승리21(국민승리21)을 확대 · 개편하여 노동자 중심의 진보 정당을 건설하기 위해 적극 지원, 연대한다”는 결의를 다졌다.
민주노동당 결성을 촉발시킨 것은 1998년 6월 4일 실시된 지방선거였다. 국민승리21과 전국민주노동조합총연맹(민주노총)은 지방선거에 49명의 후보를 내보내 기초단체장 3명, 광역의원 2명, 기초의원 18명 등 모두 23명을 당선시켰다. 이러한 성과를 바탕으로 같은 해 9월 17일 국민승리21은 중앙위원회를 개최하고, 1999년 5월까지 진보 정당을 창당하기로 공식 결의하였다.
1999년 7월 10일 국민승리21은 진보정당 준비위원회 출범을 앞두고 발전적으로 해산하였다. 이어서 8월 29일에는 창당 발기인 대회를 열고 투표를 통해 당명을 ‘민주노동당’으로 확정하였다. 다음 해 1월 30일 창당대회를 열어 진보주의 정당을 표방하며 민주노동당을 창당하였다.
민주노동당은 창당 직후 16대 총선에 참여하였다. 2000년 4월 13일 실시된 총선에서 ‘최소한 의석 1석’을 통한 원내 교두보 확보라는 목표를 내걸고 21개 선거구에 21명의 후보를 냈다. 하지만 원내 진출에 실패하였다.
민주노동당은 2002년의 지방선거와 대선에 전력을 기울였다. 같은 해 3월 16일 당대표에 권영길, 사무총장에 노회찬을 선출하였다. 6월 13일 실시된 지방선거에서 기초단체장 2명, 비례 9명 포함한 광역의원 11명을 당선시켰으며, 정당 득표율 8.13%를 기록하였다.
2002년 11월 22일 ‘2002년 대선 승리를 위한 범진보 진영 공동선거운동본부’(공선본)을 출범시켰으며, 이후 대통령 후보로 추대된 권영길은 12월 19일 실시된 대선에 출마하여 3.98%를 득표함으로써 진보 정치의 가능성을 확인시켜주었다.
이어서 2004년 4월 15일 실시된 총선거에서 민주노동당은 권영길, 조승수 등 지역구 당선자 2명과 비례대표 의원 8명을 당선시키는 성과를 거두었다. 정당 투표에서 13.1%를 기록했으며, 진보 정당 최초로 원내 진출에 성공하였다. 하지만 이때부터 민주노동당 내부의 갈등이 심화되었다.
민주노동당은 내부의 정파 갈등 구도를 극복하지 못하였으며, 특히 17대 대선을 전후하여 정파 갈등과 분열의 위기가 가속화되고 전면화되었다. 결국 민주노동당은 2008년 2월 분당을 하게 되었다. 이후 민주노동당은 2008년 4월 9일 실시된 제18대 총선에서 지역구 2석, 비례대표 3석을 차지하는 데 그쳤다.
2012년 4월에 실시되는 제19대 국회의원 선거를 앞두고 진보 대통합 논의가 활발히 일어났으며, 2011년 12월 5일 민주노동당, 국민참여당, 새진보통합연대(진보신당 탈당파) 등 3개 정파가 통합하여 통합진보당이 출범하였다. 이로써 민주노동당은 해산하였다.