사업가로서 탄탄대로가 보장되었던 김문숙은 기생관광 반대운동을 도화선으로 일본군‘위안부’문제와 만났다. 당시 부산을 포함한 서울, 경주, 제주 등에서는 일본인 남성 관광객이 한국 여성을 성적 대상으로 삼는 기생관광이 성행했다. 김문숙은 기생관광 반대운동에 참여해 여성단체들과 함께 공항에서 입국 반대 시위를 벌였다. 그런데 1990년 공항에서 기생관광 반대시위를 하던 중, 한 일본인 관광객으로부터 ‘위안부’ 여성을 언급하는 발언을 듣고 난 뒤 여성운동가를 자처했던 김문숙은 자신이 일본군‘위안부’문제를 모르고 있었다는 사실에 부끄러움을 느꼈다.12

이미 아사히신문 1985년 8월 19일자 칼럼에서 일본인‘위안부’였던 시로타 스즈코(가명)의 증언이 있었다는 것을 확인한 김문숙은, 1990년 4월 그의 진혼비가 있는 치바현 다테야마시 가니타 마을을 방문했다. 6월 27일에는 진혼비를 세운 후카츠 후미오3목사를 만났고, 이 만남을 계기로 부산항이 보이는 대청공원에 위령비 건립을 추진했다. 그러나 관련 단체의 반대로 무산되었다.

일본에 유학 중이던 장녀 김진현과 삼녀 김미현의 도움으로 김문숙은 일본 현지의 관련 장소를 찾아가고, 관계자들을 만나며 일본군‘위안부’ 문제를 직접 확인해 나갔다. 1990년 8월 21일에는 히로시마에서 파푸아뉴기니 일본군 점령의 유산과 전시 성폭력의 기억을 다룬 세키쿠치 노리코 감독의 영화 〈전장의 딸들〉을 관람하며 예술가 도미야마 다에코와 인연을 맺었다. 10월 27일에는 오키나와 도카시키섬에서 열린 태평양전쟁 희생자 합동위령제에 참석했다. 이후 도쿄 야스쿠니 신사 앞에서는 조선인 위패 반환을 요구하는 시위에 동참했고, 이 과정에서 경찰과 우익 세력의 폭력으로 아킬레스건을 다치는 부상을 입었다. 여러 사건을 겪으며 김문숙은 1990년대 일본 현장에서 일본군‘위안부’ 문제의 흔적과 전쟁 책임을 확인해 나갔다.

김문숙은 11월에 그간의 일본 방문 경험과 모은 자료들로 책 『말살된 묘비 - 여자 정신대』를 발간했다. 책의 서문에서 그는 이렇게 적었다.

1990년 한국정신대문제대책협의회 출범 이후 서울 회원으로 활동하던 김문숙은 자신의 활동 근거지이자 생활 터전인 부산에 정신대문제대책부산협의회(부산 정대협)을 설립했다. 1991년 8월 14일 김학순님이 일본군‘위안부’ 피해 사실을 공개 증언한 뒤, 김문숙은 부산에서도 피해를 알릴 수 있는 창구가 필요하다고 보았고 10월 19일 부산 정대협이 정신대 신고전화를 개통하였다. 신고전화 개통 이후 먼저 근로정신대로 끌려갔던 박수덕, 이귀분의 피해가 접수되었다. 1992년 미야자와 총리의 내한 전후 용기를 낸 피해자들의 신고가 이어졌다. 이 기간동안 하순녀, 김복동, 그리고 근로정신대였던 유찬이가 자신의 피해를 신고했다.5

12월 12일에는 「정신대 할머니 생활기금모금 국민운동 부산본부」를 발족하여 경제적으로 어려운 피해자들을 위한 긴급 지원 활동도 시작했다. 부산 정대협의 활동은 이후 관부재판, 민족과여성역사관 설립 등 여러 방향으로 확장되었다.