1946년 9월 2일 대한노총 산하 조직으로 해상노동연맹이 결성되었고, 1952년 2월 17일 전국해원조합으로 개칭하고 조직을 재정비하였다. 1953년 9월 28일 노동법이 제정되어 법에 의하여 설립된 12개 단위 노조가 참석하여 전국해상노동조합연맹을 재결성하였지만, 1960년 4·19혁명 이후 4개 노조가 전국해상노동조합연합회를 결성하여 전국해상노동조합연맹이 분열되었다.
1961년 군사정권에 의한 노동조합 강제 해산 이후 1961년 8월 19일 한국노동단체재건조직위원회에 의하여 전국해상노동조합으로 재조직되었다. 그 이후 1968년 1월 30일 노조 규약을 개정하여 산별분권체제에서 중앙집권체제로 바뀜에 따라 모든 교섭권을 전국해상노동조합이 가지게 되었다. 1969년 전국해원노동조합으로 개칭되었고, 1981년 노동조합법 개정에 따라 산업별체제에서 연맹체제로 개편되었으며, 1981년 2월 21일 전국해원노동조합연맹으로 개칭되었다. 그 뒤 1989년 전국선원노동조합으로 개칭되었다가, 다시 1998년 2월 20일 전국해상산업노동조합연맹으로 개칭되었다가 전국해상선원노동조합연맹으로 개칭하였다.
전국해상선원노동조합연맹은 다음과 같은 사업을 하고 있다. 1) 선원의 근로조건에 관한 최저 기준을 정하고 있는 선원법의 개정, 2) 선원의 권리 강화와 사회적 지위 향상을 위한 활동, 3) 선원에게 에이즈 강제 검사제도 폐지, 4) 선원의 임금 중 일정액에 대해서는 세금을 부과하지 않도록 하는 선원 비과세 제도 시행, 5) 항구에 입항하고 출항하기 위한 절차를 줄이기 위한 캠페인, 6) 오랫동안 가족들과 떨어져 지내는 선원들을 위한 가족동승제 시행 (원양어선은 가족의 ‘조업현장 방문’, 외항상선은 ‘가족동승제’), 7) 주 40시간 근로제의 도입, 8) 선원최저임금제 시행, 9) 일정 수의 한국인 선원 고용유지를 위한 지정선박제도 운영, 10) 국제 선박에 승선하는 외국인선원의 단체협약 체결 법제화. 그 밖에 부산과 인천에 국제선원복지센터를 건립하고, 전국 항구에 복지회관 건립을 추진하고 있다.
전국해상선원노동조합연맹은 2020년 현재 해운 35개, 수산 22개 총 57개 조직, 조합원 7만 명으로 구성되어 있다. 연맹의 본부는 부산 중앙동에 있으며, 서울과 인천에 각각 사무소가 있다. 선원소통매체 『월간 선원』을 발행하고 있다.