In this paper, we proposed the Dunhuang inpainting mural restoration algorithm based on the combination of sequential similarity detection algorithm and cuckoo search algorithm to improve the incorrect filling problem of the Criminisi algorithm and low efficiency in Dunhuang murals restoration. First, we improved the priority calculation formula with the method of redefining data items using a P-Laplace operator to eradicate the priority calculation tends to zero. Second, we improved the efficiency of mural restoration using the sequential similarity detection algorithm based on the dynamic threshold for searching matching blocks. To make the matching block more reasonable, we used a cuckoo optimization algorithm to determine the best matching block. Finally, mural restoration was completed through iterative updates. The results of restoration experiments on Dunhuang mural inpainting show that compared with similar comparison algorithms, the proposed algorithm in this paper achieves better subjective and objective restoration effects, and improves the restoration efficiency.