The deviation of water flow from Darcy’s flow law and the influence of stress history on the settlement of soil have been recognized by many researchers, but the theory of consolidation with the considerations of non-Darcian flow and stress history was rarely reported. Based on Terzaghi’s consolidation theory and classical Hansbo’s flow model, a nonlinear model of consolidation is developed by considering different settlement characteristics of soil with different stress states and time-dependent load in practical engineering. The finite difference method is adopted to obtain numerical solutions for this model. Based on the reliability of numerical solutions, the influences of non-Darcy flow on consolidation behavior of over consolidated soil and the influences of stress history on over consolidated soil with non-Darcy flow are intensively analyzed, and similarities and differences of consolidation behaviors are compared. The results show that the consolidation rate of over consolidated soil with non-Darcian flow is slower than that with Darcy’s flow. In addition, the consolidation rate evidently decreases with an increase in the value of m or i1. Among different stress states of soil with non-Darcian flow, the consolidation rate of over consolidated soil is the fastest, and the final settlement of over consolidated soil under external load is the smallest. When non-Darcy flow in an over consolidated soil layer is considered, a large preconsolidation pressure and a small rebound- or recompression-index always result in a rapid consolidation rate and a small final settlement.