Abstract Jordan forms of completions of partial Jordan matrices are studied. Our approach is based on an algorithm for constructing completions of a given partial Jordan matrix having prescribed eigenvalues and multiplicities. An upper bound is given for the number of entries that must be made nonzero to produce such completions. The algorithm is further interpreted in terms of the graph associated with a matrix. Some of the results are extended to a larger class of partial Hessenberg matrices.