In this study, the effect of multi-layer graphene (MLG) on the rheological behaviors of cement paste was systematically investigated. The yield stress and minimum viscosity of cement paste with MLG under different MLG contents, superplasticizer (SP) contents and water/cement (w/c) ratios were measured and compared. Based on adsorption and lubrication effects of MLG, the mechanisms of MLG on the rheological behaviors of cement paste were explained, and a prediction model of the minimum viscosity of cement paste with MLG was established. Results showed that with the increasing MLG content, the yield stress and minimum viscosity of cement paste fluctuated with an overall upward trend, which results from the competition between adsorption and lubrication effects of MLG. The water adsorption and lubrication effect of MLG have opposite mechanisms on the rheological behaviors of cement paste by affecting the internal force of cement paste and both highly depend on the MLG content. The accuracy of the proposed model of the minimum viscosity of cement paste with MLG was highly improved than the classical viscosity prediction models.