We develop a computationally efficient soft-decision Reed-Solomon (RS) decoding algorithm. Our new algorithm has direct applications to soft-decision decoding procedures such as the generalized-minimum-distance decoding algorithm. Our particular soft-decision decoding technique is not the innovation of the algorithm. The innovation is a new errors-and-erasures RS decoding algorithm that only works with different sets of erasures where the size of each set of erasures is reduced by one for each iteration (i.e., generalized-minimum-distance decoding). A result of each iteration is an error-and-erasure locator polynomial (or locator polynomials) that any RS decoder would produce. Since the new soft-decision RS decoding algorithm makes no assumptions on the d-1 erasures, the algorithm is useful for soft-decision decoding techniques such as generalized-minimum-distance decoding.>