A metric basis for a digraph G(V, A) is a set W⊂V such that for each pair of vertices u and v of V, there is a vertex w∈W such that the length of a shortest directed path from w to u is different from the length of a shortest directed path from w to v in G; that is d(w, u)≠d(w, v). A minimum metric basis is a metric basis of minimum cardinality. The cardinality of a minimum metric basis of G is called the metric dimension and is denoted by β (G). In this paper, we prove that the metric dimension problem is NP-complete for directed graphs by a reduction from 3-SAT. The technique adopted is due to Khuller et al. [Landmarks in graphs, Discrete Appl. Math. 70(3) (1996), pp. 217-229]. We also solve the metric dimension problem for De Bruijn and Kautz graphs in polynomial time. © 2014 © 2014 Taylor & Francis.