This paper presents an iterative multi-step decoding algorithm for a class of multi-step majority-logic (MS-MLG) decodable cyclic codes. The proposed algorithm is capable of efficient decoding the MS-MLG decodable cyclic codes with large number of short cycles of length 4. In addition, we decompose the parity-check matrices into several submatrices by utilizing the orthogonal structure of the codes. The decomposition scheme allows efficient decoding for MS-MLG decodable cyclic codes. Simulation results demonstrate that the MS-MLG decodable cyclic codes decoded with the proposed algorithm outperform BCH codes with similar lengths and rates decoded with the hard-decision algorithm.