Abstract: IB method employs the joint probability distribution between the source variable and the relevant variable to maximally compress the source variable, such that the middle compression variable can maximally save the information about the relevant variable. As a result, this method gives birth to several effective iterative algorithms, in which, the sequential IB algorithm (sIB) is one of the better and widely applied IB algorithms. But this algorithm also has some limits, such as, low efficiency and insufficient optimization, etc. For the sake of solving these problems of the sIB algorithm discovered in applications, an iterative sIB algorithm (isIB) based on mutation method is proposed here. Firstly, relevant experiments for selecting reasonable mutation rate are conducted. Based on this rate, the isIB algorithm chooses random proportional positions from the initial solution vector resulting from a seeding sIB algorithm, and randomly mutates the corresponding mapping relation from these chosen positions to the clustering labels. After getting the initial solution, the isIB algorithm optimizes it iteratively. The experimental results on the benchmark data sets indicate that the proposed isIB algorithm outperforms the sIB algorithm in both the accuracy and the efficiency.