An error correction circuit and method for reducing a miscorrection probability and a semiconductor memory device including the circuit are provided. The error correction circuit includes an error check and correction (ECC) encoder and an ECC decoder. The ECC encoder generates syndrome data enabling h-bit error correction based on information data and a generator polynomial, where “h” is 2 or an integer greater than 2. The ECC decoder may operate in a single mode for detecting an error position with respect to a maximum of (h−j) bits in the information data based on encoded data including the information and the syndrome data, where “j” is 1 or an integer greater than 1. Alternatively, the ECC decoder may operate in a first operation mode for detecting an error position with respect to a maximum of “h” bits in the information data or in a second operation mode for detecting an error position with respect to a maximum of (h−j) bits in the information data based on encoded data including the information and the syndrome data. Accordingly, the miscorrection probability is reduced, and therefore, data reliability is increased.