• The MPFrDTMs and their inverse process are put forward. • A new nonlinear fractal permutation method is constructed by combining the FSTM with the rotation operations. • A novel color image encryption scheme is presented by combining the MPFrDTMs and the nonlinear fractal permutation method. A novel color image encryption scheme is presented by combining the multi-parameter fractional discrete Tchebyshev moments (MPFrDTMs) with the nonlinear fractal permutation method. To withstand the brute-force attack on the image encryption algorithm based on the fractional discrete Tchebyshev moments, the MPFrDTMs and their inverse process are put forward for larger key space. Furthermore, a new nonlinear fractal permutation method is constructed by combining the fractal Sierpinski triangle model (FSTM) with the rotation operations. The structural complexity of the FSTM directly determined by the plaintext image could resist known-plaintext attack and chosen-plaintext attack. Simulation results and performance analyses illustrate that the proposed color image encryption scheme is feasible and has a high level of security.