An ordered graph is a graph enhanced with a linear order on the vertex set. An ordered graph is a core if it does not have an order-preserving homomorphism to a proper subgraph. We say that H is the core of G if (i) H is a core, (ii) H is a subgraph of G, and (iii) G admits an order-preserving homomorphism to H. We study complexity aspects of several problems related to the cores of ordered graphs. Interestingly, they exhibit a different behavior from their unordered counterparts. We show that the retraction problem, i.e., deciding whether a given ordered graph admits an order-preserving homomorphism to a specific subgraph, can be solved in polynomial time. On the other hand, it is NP-hard to decide whether a given ordered graph is a core. In fact, we show that it is even NP-hard to distinguish graphs G whose core is largest possible (i.e., if G is a core) from those whose core is the smallest possible, i.e., its size is equal to the ordered chromatic number of G. The problem is even W[1]-hard with respect to the latter parameter.