The legal firing sequence problem of Petri nets (LFS) is one of fundamental problems in the analysis of Petri nets, because it appears as a subproblem of various basic problems. Since LFS is shown to be NP-hard, various heuristics has been proposed to solve the problem of practical size in a reasonable time. In this paper, we propose a new algorithm for this problem. It is based on the partial order verification technique, and reduces redundant branches in the search tree. Moreover, the proposed algorithm can be combined with various types of heuristics.