인천 강화군의 석모도에서 태어났다. 아버지는 태평양 전쟁 기간 중 징병되어 참전하였고 누이는 일본인 선박 자본가의 집에 가정부로 팔려가는 등 몹시 가난한 농가에서 자랐다. 

1950년 한국 전쟁 중 강화도를 점령한 조선민주주의인민공화국이 토지개혁을 실시하여 1,500평의 토지를 분배 받자 조선인민군에 자원입대하여 월북하였다. 이후 조선민주주의인민공화국에서 결혼하고 정착하였다가 공작원으로 남파되었다.

체포되어 대전교도소 수감 중 전향을 권유받았으나 거부하여 비전향 장기수가 되었다. 최선묵은 이때 교도소 재소자로 구성된 전향공작반에게 심한 구타를 동반한 고문을 받았고 이로 인해 사망한 동료도 있었다고 주장했다. 총 복역 기간은 약 38년으로 비전향 장기수 가운데서도 긴 편에 속한다.

출감한 뒤 대전에서 다른 장기수들과 함께 탕제원을 운영하며 생활 하던 중, 2000년 6·15 남북 공동선언에 의해 조선민주주의인민공화국으로 송환되었다. 가족과 다시 만나 평양에서 거주하였고 서예작품전을 열며 서예가로 활동하였다. 

2005년에는 《로동신문》에 〈선군화원에 꽃들은 만발한다〉라는 수기를 발표하여 김정일의 선군 정치와 여성 정책에 지지를 표명했다. 최선묵의 삶을 소재로 한 장편소설 《밭갈이 노래》가 창작되기도 했다.
2005년에 <선군화원에 꽃들은 만발한다>라는 글이 실린 언론은?
《로동신문》 로동신문