In view of the insufficient consideration of structural information in the priority calculation of the Criminisi image inpainting algorithm and the fact that matching only relies on the color distance selection, the mural repair process is prone to structural propagation errors and pixel mismatches. To address this, a mural inpainting algorithm based on information entropy and structural characteristics is proposed in this study. First, when calculating the priority function, the information entropy of measuring the complexity of the pixel block is introduced, and the optimal block to be repaired is determined by improving the priority function to preferentially repair the regions with rich structural information. Then, the matching block is determined by combining the sample color feature and the covariance similarity between blocks, and then the best matching block is determined through the Euclidean distance between the blocks. Finally, the mural inpainting is completed through iterative updating. Experiments on damaged Dunhuang murals show that the proposed algorithm overcomes the problem of the Criminisi algorithm mismatching and filling. Subsequent to the repair, good visual effects are obtained, and objective evaluation values such as peak signal-to-noise ratio of the image are improved.