1961년 5·16군사쿠데타로 인해 그 해 8월 3일 근로자의 단체활동에 관한 임시조치법이 공포됨으로써 노동조합이 전면 해체되었다. 동년 9월 14일노총재건조직위원회의 위촉을 받아 전국연합노동조합 결성준비위원회가 구성되고 9월 21일 노총 산하 13개 산업별 노동조합에 속하지 않는 각 사업장의 노동자 대표 30명이 참석하여 전국연합노동조합을 결성하였다. 조합활동 1년의 기간 동안 그 조직은 13개 지부, 27개 분회, 28개 지회, 1만 6천여 명이 되었다.
그 뒤 노동관계법의 전면적인 개정에 따라 1981년 2월 24일한국노총 대강당에서 제19차 정기 전국대의원대회에서 조합의 명칭을 ‘전국연합노동조합연맹’으로 개칭하였다.
1987년 노동자 대투쟁으로 노동운동이 폭발적으로 전개됨에 따라, 조직수가 급격히 증가하여 1989년에는 1,357개 조직, 16만 1천여 명에 이르렀지만, 1992년 병원노련, 전문기술노련, 건설노련 등의 조직 탈퇴로 1999년 12월말에는 412개 조직, 5만 4,420명의 조합원으로 급속하게 줄어들었다.
2000년 이후 필요에 의거 설치됐던 업종별 분과위원회(환경, 아파트)를 확대 개편하여 환경, 아파트, 공공서비스, 기술, 목가공, 식품, 유통서비스, 의료, 시설관리, 제조, 항공·운수, 건설 등 12개 분과위원회를 조직하였다.
2009년 12월 현재 조합원수는 320개 조직 48,985명이다.
1987년부터 환경미화원 임금과 관련하여 행정안전부와 지속적인 협의를 추진하여 왔다. 그 결과 기존에는 환경미화원의 임금이 일당제 동일 임금 지급방식이었으나, 2005년에 월급제로 전환되었고, 2008년에도 완만한 호봉임금제로 전환되도록 하였다. 그 밖에 건물관리, 청소용역, 지하철 청소용역 등 서비스분야 노동자의 저임금 해소를 위하여 노동부 등 정부 기관에 정책 건의를 지속적으로 하고 있다.
2010년 현재 현장 활동을 강화하여 한국노총 법률원, 전국연합노동조합연맹 그리고 현장 사업장 노조 간 법률자문계약을 체결하여 지원활동을 강화하고 있다.
현재 상급 단체는 한국노동조합총연맹이며, 국제건축목공노련(IFBWW)에 가맹하고 있다.
전국연합노동조합연맹은 전국에 산재하고 있는 다양한 업종의 조합원수가 10여 명에 불과한 노동조합에서 수천 명에 이르는 노동조합까지 포괄하고 있다.