A Distance Realization problem asks, given an \(n\times n\) matrix D of nonnegative integers, to find an n-vertex graph G and an integral weight function on the edges realizing D, i.e., such that \(dist_G(i,j)\) , the weighted distance from i to j, equals \(D_{i,j}\) for every i and j, or decide that no such realizing graph exists. This paper introduces and studies the Minimum Deviation Distance Realization optimization problem, where given a matrix D, the goal is to find a weighted graph (G, w) that realizes D as closely as possible, i.e., such that the deviation \(\phi (D,G)\) between D and the matrix of pairwise distances in G is minimized. We focus on four different types of deviation functions \(\phi \) : the maximum difference over all matrix entries, \(\phi _{\textsc {max}}\) , the sum of differences of all matrix entries, \(\phi _{\textsc {sum}}\) , the number of matrix entries exhibiting a mismatch, \(\phi _{\textsc {num}}\) , and the multiplicative difference over all matrix entries, \(\phi _{\textsc {mult}}\) . For each deviation function \(\phi \) , we consider the following variants of minimum deviation distance realization problems: (i) The deviation of the realizing graph (G, w) from the matrix D is allowed to be only upwards, only downwards, or in both directions; and (ii) The entries of D may specify exact values or ranges of permissible values. For each problem in this wide spectrum of variants, we either present a polynomial-time algorithm or show hardness and give a polynomial-time approximation algorithm.