김문숙은 1927년 1월 12일 경북 영천에서 2남 4녀 중 첫째로 태어났다. 아버지는 조선미곡창고주식회사(현 CJ대한통운)의 관리직으로 근무했고, 어머니는 아들과 딸을 차별 없이 키우며 교육시켰다. 그는 여성운동의 모태가 어머니였다고 기억한다.

1939년 영천공립보통학교를 졸업한 김문숙은 1943년 경북공립고등여학교(현 경북여고)를 졸업한 후 같은 해, 이화여자대학교 약학과에 진학하였다. 하지만 전쟁 말기, 여학생들조차 결혼을 하지 않으면 끌려갈 수 있다는 불안 속에 학업을 마치기는 어려웠다. 해방 후에도 정치적 혼란이 이어지자 김문숙은 고향인 대구로 돌아와 경북중등교원 양성소 지리학과로 학교를 옮겨 학업을 마무리할 수 있었다. 이후 진주공립여자중학교에서 교사로 부임했다.

1950년 대구에서 결혼한 김문숙은 한국전쟁으로 인해 부산에 정착하게 되었다. 대연동·망미동으로 거쳐 세 딸과 두 아들을 키우며 1950년대를 보냈다. 1965년 김문숙은 부산 중앙동에 (주)아리랑관광여행사를 창업하며 사업적 성공을 이끌었다. 부산에서 운영된 주식회사 중 최초로 여성이 대표를 맡은 사례였다. 1986년 부산여성경제인연합회 회원들이 기금을 마련하여 개통한 〈여성의 전화〉를 운영하면서 간행물〈여성의소리〉발행인으로도 활약했다. 설립 후 1년 만에 상담 건수가 1,200여 통을 넘길 정도로 〈여성의 전화〉는 부산과 인근 소도시 여성들의 호응이 컸다.

창립 후 10년간 부산 〈여성의 전화〉는 성폭력, 가정폭력 상담뿐만 아니라 피해자 재판 지원과 여론 형성 등 성폭력·가정폭력 사건 지원 활동에도 적극 참여하였다. 피해자를 위한 적절한 쉼터가 없던 시절, 김문숙은 자주 자신의 자택을 피해자들의 쉼터로 제공했다.

1991년 10월 19일, 김문숙은 〈여성의 전화〉를 운영하는 동시에 ‘정신대 신고전화’를 개통하며 일본군‘위안부’피해자들의 피해 사실을 알릴 수 있게 하였다. 이는 후에 관부재판의 발판이 되었다.