This paper reports impossible differential cryptanalysis on the 128-bit block cipher CLEFIA that was proposed in 2007, including new 9-round impossible differentials for CLEFIA, and the result of an impossible differential attack using them. For the case of a 128-bit key, it is possible to apply the impossible differential attack to CLEFIA reduced to 12 rounds. The number of chosen plaintexts required is 2118.9and the time complexity is 2119. For key lengths of 192 bits and 256 bits, it is possible to apply impossible differential attacks to 13-round and 14-round CLEFIA. The respective numbers of chosen plaintexts required are 2119.8and 2120.3and the respective time complexities are 2146and 2212. These impossible differential attacks are the strongest method for attacking reduced-round CLEFIA.