A Reed-Solomon (RS) decoding apparatus having high error correction capability and a method thereof are provided. The apparatus includes: error location and analysis polynomial generating units for performing a modified Euclid algorithm by receiving syndrome data upon receipt of an enable signal, and suspending input of the syndrome data and outputting error location polynomial data and error analysis polynomial data by executing the modified Euclid algorithm independently upon receipt of a disable signal; a controlling unit for controlling the error location and analysis polynomial generating unit and the input of the syndrome data; and switching units for providing the syndrome data to corresponding error location and analysis polynomial generating unit upon receipt of the enable signal and controlling the input of the syndrome data upon receipt of the disable signal. The number of the switching units is identical to that of the error location and analysis polynomial generating units.