In this paper, the problem of termination of rewriting in order-sorted algebras is addressed for the first time. Our goal is to perform termination proofs of programs for executable specification languages like OBJ3. An extension of Lexicographic Path Ordering is proposed, that gives a termination proof for order-sorted rewrite systems, that would not terminate in the unsorted case. We mention also, that this extension provides a termination tool for unsorted terminating systems, that usual orderings cannot handle.