대한체신노동조합(현재 전국우정노동조합)은 1958년 3월 24일 대한노총 산하 산업별 노동조합으로 창립되었다. 그 해 5월까지 서울·부산·광주·대전지부 등 하부조직을 결성하고, 7월 세계 각 국의 우편·통신 분야의 노동자들이 가입되어 있는 국제체신노련(Communications International)에도 가맹하였다. 1959년 전국체신노동조합으로 개칭하였다. 창립 이후 매년 정기적인 단체교섭 및 노사협의회를 개최하여 조합원의 임금인상과 근로조건 및 제도의 개선을 추진하였다.
1961년 5월 포고령 6호에 의거 해체되었다가, 8월 16일 전국체신노동조합으로 노조를 재건하였다. 1976년 권중동 위원장이 국회의원이 되었다. 1979년에는 잡급직 퇴직금지급 청구소송을 제기하여 정부기관에 고용되어 있던 3만여 명의 잡급 직원을 정규직 공무원으로 전환시키는데 성공하였다.
1982년 1월 한국전기통신공사가 발족하여 전국우전통신노동조합 연맹 산하 단위 노동조합으로 명맥만 유지하다가 1987년 12월 우전통신연맹을 탈퇴하여 산업별 노조로 출범하였고, 1988년 2월 한국노총에 가입하였다. 1989년 헌법재판소의 출범과 동시에 공무원의 쟁의행위를 금지하고 있는 노동쟁의조정법 제12조 제2항에 대한 헌법소원을 제기하여 헌법불합치 결정을 얻어냄으로써 공무원노조의 단체행동권을 회복하게 되었다. 이와 함께 조합원의 조합 의식 고취와 일선 조합간부 양성을 위한 교육사업도 지속적으로 실시하였고, 각종 회의와 대회를 통한 조직 강화 활동도 활발히 벌였다.
1990년대에 들어서는 정보통신부 산하단체인 체신공제조합·우정사업진흥회 및 체성회 등에 구성된 노동조합을 산하조직으로 차례로 가입시켜 조직을 확대하였다. 1999년 5월 한국노총과 공동으로 2만여 조합원 가족 등이 참여한 ‘인력감축 철회 및 생존권 사수 궐기대회’를 개최하였다.
2001년 4월 상시 위탁 집배원의 노조 가입 자격을 부여하였으며, 7월에는 노사정위 공공특위에서 3,756명 인력감축을 중단하는 합의를 이끌어내었다. 2006년 양대 노총의 근로기준법 개악 저지 투쟁대회, 공무원연금 등 특수연금 개악 저지를 위한 공동대책위원회에 참여하였다. 2008년에는 정부의 우정사업 민영화 정책에 반대하여 공사화 저지 비상대책위원회를 구성하여 활동하여 민영화를 저지하였다.
2011년 현재 전국우정노동조합은 1개 노조, 2만 6천여 명의 우정 종사원으로 구성된 전국규모 단일노조로 활동하고 있다.