1967년 5월 30일 전국철도노동조합 대의원대회에서 전국관광노동조합을 설립하기 위해 철도 관광지부를 해산하고, 1967년 6월 9일 전국관광노동조합 창립준비위원회를 구성하여 노조 설립을 추진하였지만, 노동청의 노조 설립 신고 반려로 행정처분취소 소송을 하여 승소하였다. 1970년 12월 12일 국제관광공사 산하의 반도호텔, 워커힐호텔, 대한여행사, 아리랑택시운수사업소, 외래품판매업소 등의 노동자를 중심으로 산업별 노동조합으로 전국관광노동조합을 결성하였다.
1980년 노동관계법 개정에 따라 1981년 2월 24일 기업별 단위 노동조합 연합체로 개편하여 전국관광노동조합연맹으로 개칭되었다. 전국관광노동조합은 출범 당시 8개 업체의 1,800명의 조합원에 지나지 않았지만, 관광산업의 급격한 성장에 따라 1990년에는 전국의 관광호텔을 비롯하여 레저산업·여행알선산업·관광교통업·토산품판매업·삭도업(索道業)·요식업, 그 밖의 관광 관련 서비스업에 종사하는 약 140개 단위 노조, 2만 5,000명의 조합원을 포괄하게 되었다.
2002년 4월 전국관광산업노동조합연맹과 통합하여 워커힐호텔, 조선호텔, 그랜드하얏트호텔, 프라자호텔 등 주요 특급 호텔 노조들이 대거 가입하게 되었다. 2005년 6월 14일 ‘특수고용직 노동3권 쟁취 투쟁’ 중 수안보파크호텔 노동조합위원장 겸 한국노총 충주지역지부 지부장인 김태환이 사조레미콘의 대체 용역 기사의 차에 치여 사망하는 사건이 일어났다. 한국노총은 사단법인 김태환기념사업회를 설립하였다.
2010년 현재 전국관광·서비스노동조합연맹은 74개 노조로 조직되었으며, 15,523명의 조합원 대부분은 호텔 노동자들이다.