호는 매헌(梅軒). 경기도 안성 보개면 출생.
김숙자의 조부 김석창(金碩昌)은 경제(京制) 명창이었고, 부친 김덕순(金德順)은 판소리, 경기무악, 민속악의 재인으로 화성 재인청과 안성 신청에 속했으며, 모친 정귀성(鄭貴星)은 세습무 계열이었다. 6살부터 아버지에게 판소리와 춤, 무속을 배우기 시작했으며, 11세부터는 줄타기도 배워 17세까지 줄을 탔다. 1942년 안성 어녀리굿판 이후 굿이 금지되면서, 숨어다니면서 아버지에게 기예를 배웠고 수원권번 소리선생 조진영(趙鎭英)에게 소리와 춤도 배웠다.
1946년에 서울에서 무용연구소를 냈으나 경영이 어려웠고, 1961년 대전에서 국악학원 시절에 창무극 「이순신」으로 문공부 추최 전국신인국극경연대회에서 수상하였으나 주목받지 못했다. 1963년에 다시 서울에 올라와 김숙자민속무용학원을 차리고 제자들을 가르쳤다.
1976년에 이르러 정병호와 심우성의 주선으로 올린 공간사랑의 공연에서 올림채, 터벌림, 진쇠, 제석춤, 부정놀이, 군웅춤을 추면서 알려지기 시작했다. 1979년에 한국무속예술보존회를 창립해서 매년 무속예능인을 공연하게 하였고, 본인은 국내외에서 수많은 공연을 하였다.
1980년대 중반에 교통사고와 세 번의 대수술을 치뤘지만 다시 무대에 섰고, 1990년에 국가무형문화재(현, 국가무형유산) 「살풀이춤」(경기도 도당굿 도살풀이)의 예능보유자로 지정되었다. 김숙자의 춤은 무대쪽에서 보면 굿판에 가깝고, 굿쪽에서 보면 무대와 가깝다. 김숙자 사후 김운선과 양길순이 예능보유자로 지정되었다.
2003년 옥관문화훈장