On-orbit maintenance is essential to maintain the safe operation of space stations in special environment of outer space. The harsh space environment and the structural characteristics of space stations determine on-orbital maintenance operation complexity (OOMOC), which is related to the optimization of maintenance program, the development of maintenance plan, the arrangement of cargo spacecraft, astronaut training and space station maintainability design. However, there are few studies on OOMOC. In this paper, we proposed the concept of OOMOC, and established a complexity evaluation model based on information entropy theory. The model is composed of the instinct maintenance complexity and the external impact factors. Maintenance logic, the number of maintenance operations, human machine interface (HMI) for maintenance and knowledge support were considered by the instinct complexity, and quantified with information entropy; the external influence factors covered operation space, tool support, time pressure, visual occlusion and impact of spacesuits, and were quantified with a graded scoring method. To verify model, the maintenance test for 12 types of product based on the ground simulation cabin was performed, and maintenance actions and duration were collected. The experimental results show that the proposed model can better quantify OOMOC and predict maintenance operation time (correlation coefficient is 0.82). This paper can also provide methodological guidance for on-orbit maintenance, evaluation of maintenance programs, astronaut crew training, and space station maintainability design.