In this paper we develop a primal–dual simplex algorithm for the bi-objective linear minimum cost network flow problem. This algorithm improves the general primal–dual simplex algorithm for multi-objective linear programs by Ehrgott et al. (J Optim Theory Appl 134:483–497, 2007). We illustrate the algorithm with an example and provide numerical results.