The Multi-objective Integer Minimum Cost Flow Problem (MOIMCF) asks for the efficient integer flows of a capacitated network whose arcs carry vectors of conflicting costs. We present an exact algorithm that computes a minimal complete set of efficient flows, based on a characterization of efficiency by circulations in the residual network. The feasible set is partitioned by integer bound decisions on single arcs, and each partition is represented by its lexicographically minimum flows for the q cyclic orders of the objectives, which give its ideal point and are obtained for each child by lexicographic shortest augmenting paths. The main result shows that a partition can have a new nondominated vector in a box of the search region only if the residual network of any of these representatives contains a lexicographically negative cycle for weights determined by the box and by the representative. One negative-cycle detection per box therefore either returns a circuit directed at the box, which is used to branch, or certifies that the partition and all its subpartitions have no vector in the box. Computational experiments with three to five objectives compare the method with two general multi-objective integer programming algorithms. The method is faster than both on most instances, with an advantage that is larger with four and five objectives; with three objectives, the defining point algorithm is faster on dense networks with large supply.