A new soft-input soft-output (SISO) decoding algorithm based on minimum distance search (MDS), called SISO-IMDS, is presented. The bit error rate of the proposed SISO decoding algorithm is almost the same as those of Max-Log-MAP and Log-MAP algorithms. Moreover, the average decoding complexity of the MDS based SISO decoding algorithm is much smaller than those of trellis-based SISO decoding algorithms. Consequently, the proposed SISO-IMDS can be applied in practical iterative decoding algorithms for a product code and a block turbo code.