IMF 외환 위기 속에서 1998년 출범한 김대중 정부는 최초로 수평적 정권 교체를 이룬 ‘국민의 정부’였지만 집권 여당의 의석 기반은 미약하였다. 김종필 총재의 ‘ 자유민주연합’(자민련)과 공동 정부를 구성해서 통치하였다.
제16대 국회의원 선거 국면이 되자 국민회의와 자민련의 이해가 첨예하게 충돌하였다. 1998년 6월 4일 수평적 정권 교체 후 치러진 첫 지방선거에서 공동 여당인 국민회의와 자민련은 연합 공천을 통해 승리하였다. 공동 여당은 수도권을 휩쓸고 전국 10개 지역[국민회의 6, 자민련 4]에서 당선자를 냈다. 반면 한나라당은 부산, 대구, 경북 등 영남권 6개 지역에서 승리하였다.
16대 총선을 앞두고 국면 전환이 필요하였다. 자민련과의 공조에는 한계가 있으니 독자적으로 안정적인 의석을 확보하여 소수정권을 탈피해야 하였다. 새로운 인재들을 충원하여 전국 정당으로 거듭나기 위해서는 신당이 필요하였다.
국민회의 총재인 김대중 대통령이 직접 나서 ‘중산층과 서민 중심의 개혁적 국민 정당’인 신당을 구상하고 추진하였다. ‘인권과 복지를 중시하는 정당’, ‘지역 구도를 타파하는 전국 정당’, ‘21세기 지식 기반 시대를 이끌고 갈 정당’을 만들기 위해 신망 있는 인사와 각계의 전문가, 활력 있는 젊은 층을 전국적으로 영입하였다.
개혁적 보수 세력과 건전한 혁신 세력까지 받아들여서 폭넓고 튼튼한 정당을 만들고자 하였다. 여성 지도자들을 적극 영입하고 여성에게 비례대표 의석의 30%를 배정하였다.
2000년 1월 20일 민주주의, 시장경제 그리고 생산적 복지를 이념적으로 지향하는 개혁 정당인 ‘새천년민주당’을 창당하였다. 창당 대회에서 김 대통령을 총재로 추대하였다. 이로써 78명의 의원으로 수평적 정권 교체를 실현시킨 정당 새정치국민회의는 해체되었다.
16대 총선에서 여당인 민주당은 비교적 선전하여 115석을 차지하였다[지역구 96석, 비례대표 19석]. 공동 여당인 자민련은 17석만을 얻어 총선 전 55석에서 무려 38석을 잃었다[지역구 12석, 비례대표 5석). 한나라당은 133석을 확보하여 과반에 단 4석이 모자랐다[지역구 112석, 비례대표 21석]. 민주당의 선전에도 불구하고 공동 여당인 자민련의 몰락으로 야당인 한나라당이 국회 주도권을 갖게 되었다.
16대 국회의 마지막 해인 2004년에 노무현 대통령 당선 이후 새천년민주당에서 분당하여 열린우리당이 창당되자 노무현 대통령 탄핵 사태를 주도하였다. 탄핵 역풍으로 2004년 치러진 17대 총선에서 지역구 5석, 비례대표 4석 총 9석밖에 얻지 못하는 참패를 겪었다. 2005년 5월 6일 민주당으로 당명을 변경하고, 2007년 6월 27일 ‘중도통합민주당’으로 합당하여 해산하였다.
새천년민주당의 당원은 열린우리당, 민주당, 국민통합21로 나뉘어 이후 정치 활동을 이어갔다.
김대중 대통령 집권 이후 의회 기반을 강화하기 위해 집권 여당인 새정치국민회의를 해체하고 창당하였다. 그렇지만 지역주의 벽을 넘지못하고 오히려 호남 지역주의에 갇히면서 몰락의 길을 걷게 되었다.