조선로동당 내에는 대외연락부(사회문화부), 통일전선부(통전부), 작전부,35호실(대외조사부) 등 4개의 대남 관련 부서가 존재해 왔다. 그 중 대외연락부는 남한 내 지하당 구축을 전담해 온 대표적인 대남 부서이다.
통일전선부는 대남 외교를 주관하는 부서로서, 남북정상회담 이후 남북 간의 접촉과 교류·협력의 전면에 나서고 있는 관계자들이 전부 통일전선부 소속이다. 35호실은 해외 정보를 수집하고 해외 인사를 포섭·매수해 남한에 투입시키는 등 제3국에서의 대남 사업을 주관하며, 작전부는 남한 내 고정간첩을 통한 정보 획득이나 임무 부여, 대남 침투요원 안내 및 호송 요인 저격·납치 등을 맡고 있는 것으로 알려져 있다.
1947년 북조선로동당 ‘5과’로 창설되었다. 6·25전쟁기 남한지역 내 게릴라부대의 지하당 공작 과정에서 대남 공작기구를 확대하면서 당 조직부 내의 연락부를 분리했다. 1961년 4차 당대회에서 남한에서의 지하당 조직 확대와 통일전선 강화 등의 결정과 함께 내무성 등의 대남 공작기구를 통합해 중앙당 ‘연락국’을 신설했다. 1964년 2월 조선로동당 중앙위원회 4기 8차 전원회의에서 ‘3대 혁명력량 강화’노선을 채택하면서 종래의 연락국을 ‘대남사업총국’으로 개칭했다.
1966년 10월 12일 당 중앙위원회 4기 14차 전원회의에서 비서국이 신설되면서 대남사업담당비서 산하에 ‘연락부’, ‘문화부’, ‘조사부’, ‘인민무력부정착국’, ‘조총련’부서를 두었으며, 1978년 1월 통일전선부가, 1990년대 후반 35호실(대외정보조사부)과 작전부가 신설됨으로써 대남 담당 부서의 체계가 구축되었다. 남한 내 정당, 사회단체, 군부에 대한 공작 거점 및 공작 전술 연구개발 업무를 수행하고 있다. 특히 간첩교육과 파견을 직접 담당하고 있으며, 조총련에 대한 활동 지도도 담당하고 있다.