For every connected graph G, a subgraph H of G is isometric if for every two vertices x, y ∈ V (H) there exists a shortest xy-path of G in H. A distance-preserving elimination ordering of G is a total ordering of its vertex-set V (G), denoted (v1, v2,. .. , vn), such that any subgraph Gi = G \ (v1, v2,. .. , vi) with 1 ≤ i < n is isometric. This kind of ordering has been introduced by Chepoi in his study on weakly modular graphs. In this note we prove that it is NP-complete to decide whether such ordering exists for a given graph — even if it has diameter at most 2. Then, we describe a heuristic in order to compute a distance-preserving ordering when it exists one that we compare to an exact exponential algorithm and an ILP formulation for the problem. Lastly, we prove on the positive side that the problem of computing a distance-preserving ordering when it exists one is fixed-parameter-tractable in the treewidth.