변화당 주도의 정당연합은 2022년 12월부터 처음 논의된 바 있다. 당시에는 제3지대·진보를 포괄하는 초당적 정당 연합체를 추진하려 했는데 내부 검토 후 구체적인 방안을 다시 제시하기로 하여 폐기되었다. 그러던 2023년 3월, 상반기 재보궐선거를 앞두고 변화당과 진보당이 단일화 합의에 이르는 과정에서 정당연합이 다시 떠오르기 시작했고, 4월 15일 당 내 토론회를 통해 탈(脫)위성정당 및 범진보 포괄 정당연합 추진을 당론으로 확정, 본격적인 범진보 정당연합 구상에 들어간다. 당 관계자는 변화당 뿐만이 아닌 모두가 정당연합의 구심점이 되어야 한다며 이를 주장했다고 한다.
2023년 4월 26일 변화당-민주노총 간 공동 간담회에서 양측 모두 불평등 타파, 한국 사회 대전환, 진보정치 대단결이란 공통된 의견을 바탕으로 범진보 정당연합 추진에 긍정적 의사를 보였으나, 민주노총이 가설 정당을 만들자는 안을 제시하면서 방법론에 대한 이견을 보였다. 그럼에도 민주노총이 변화당 안을 수용해 정당연합 구상을 돕는 대신, 진보 4당과 시민사회가 참여하는 정당연합을 만들어 달라는 의견을 받아들이면서 의견 합의에 성공했고, 나중에 진보당, 노동당, 녹색당, 정의당을 설득해 5자 실무 협의를 6월 초부터 진행하기로 했다.
2023년 5월 30일 변화당에서 자당이 제시한 정당연합 구상 방안 및 참여를 놓고 실시된 당원총투표에서 93.8%가 찬성, 5.2%가 반대로 나타나, 이 구상대로 정당연합을 만드는 동시에 정당연합 참여가 확정되었음을 밝혔고, 같은 날 5당 모두 정당연합 실무회의에 긍정적인 의사를 밝히면서 6월 1일로 개최가 확정되었다.
2023년 6월 1일 변화당, 진보당, 녹색당, 노동당, 정의당이 참여한 "진보진영 승리를 위한 정당연합 추진 공동실무회의"가 열리면서, 정당연합의 구체적인 방안과 선거 전략 등 다양한 의견을 제시했다. 그 결과 정당연합의 형태는 변화당이 제시한 안을 유지하기로 하고, 지역구 단일 후보 공천과 비례 교차 투표를 선거 전략으로, 노동·환경·복지를 우선순위로 하여 정책을 통일하자는 의견이 도출되었다. 한편 정당연합이 실패할 경우를 대비해 선거연합정당안을 구상하는 것에 대해서는 부정적 의견을 피력한 변화당을 제외한 4당이 깊은 관심을 보이기도 하였으나 최종적으로 폐기되었다.
실무회의 이후 4당은 변화당의 정당연합 구상안의 실효성과 가치 여부를 확인하는 내부 의견을 거친 끝에 각각 6월 9일(녹색당), 6월 15일(정의당), 6월 22일(진보당), 6월 29일(노동당)에 당원총투표를 열었으며, 각각 89%, 63%, 94%, 92%로 참여가 확정되었다. 다만 정의당은 제3지대 재창당론과 맞물리고, 세 번째 권력의 반발로 참여에 차질이 빚어지고 있어 이에 대한 대책이 필요하다는 의견도 나온다. 이후 7월 18일 명칭을 민주사회단일화연대로 확정하는 동시에 미래당이 새로 합류했고, 7월 22일에는 정의당이 제3지대론로 인한 당 내 갈등과 정당연합 작업 지체를 우려해 6개 정당이 합의하며 민사련을 탈퇴했다.
2023년 8월 1일 고양시 일산서구 KINTEX 제1전시장 제1홀에서 출범식을 거행해 정식 출범을 선언했다. 출범식에서는 5당의 대표는 물론 강성희·심상정 국회의원, 이백윤 노동당 부대표, 강신표 한국노총 부위원장, 전종덕 민주노총 부위원장, 홍세화 장발장은행장, 권영길 나아지는 살림살이 이사장 등이 참여하였으며, 선언문에서 국내외 사회 운동의 모든 정신적 흐름과 진보정치의 역사를 계승하는 한편 "대중적 진보진영 정당연합조직"임을 재확인해 연대와 모색을 촉구했다.
다만 출범 직후 너무 이른 시기에 나온 것이 아니냐는 내부 의견이 나오면서 5당 측 대표 전원의 당직자회의를 통해 2024년 1월까지 활동을 잠정 중단하기로 결정했는데, 이 과정에서 내부 논쟁이 일어났다. 찬성 측은 총선 승리가 목적이기 때문에 공식적인 활동을 하는 것은 아직 시기상조이며, 잠시 활동을 멈추었다가 연말에 재개하자는 의견인 반면, 반대 측은 갑작스럽게 활동을 중단하는 것이 정당연합으로서의 의미가 없고, 10월에 있을 강서구청장 재보궐선거부터 단일 후보를 내야 한다는 입장이다. 5당 측은 우선 이들을 진정시키기 위해 중재 역할을 할 것으로 알려졌으며, 재보궐선거 단일화는 개별적으로 치를 것으로 보인다.
그런데 강서구청장 보궐선거 이후 진보 단일화의 실패가 부진의 원인으로 지목되면서, 민사련의 활동을 즉각 재개해달라는 내부 의견이 잇따랐다. 또 정의당이 선거연합정당으로 방향을 틀면서 민사련 지지자들과 녹색당의 비판을 받은 끝에 11월 2일 대표의 기자회견으로 무산되자 이에 대한 필요성이 커지기 시작했고, 결국 2023년 12월 9일 명칭을 민주진보연대로 바꾸고 다음 날인 12월 10일 총선기획단 체제로 전환함으로써 사실상 공식 활동을 재개하였다.