RePOP challenges the prevailing pessimism about the scalability of partial order planning (POP) algorithms by presenting several novel heuristic control techniques that make them competitive with the state of the art plan syn-thesis algorithms. Our key insight is that the techniques responsible for the efficiency of the currently successful planners, viz., the distance based heuristics, the reachability analysis and the disjunctive constraint handling--can also be adapted to dramatically improve the efficiency of the POP algorithm. We implement our ideas in a variant of UCPOP called RePOP and show that RePOP out-performs Graphplan (GASP!) in "parallelizable" domains, while retaining the advantages of concurrency and execution flexibility.