The study of the rheological properties of cement-based materials is essential to the processes directly linked to the flow performance of the fresh mixture. As well, the use of micro- and nano-cellulose-based materials is gaining visibility in its application within cementitious matrices. Despite the great potential represented by those materials, there are still informational gaps to be filled. This work aims at exploring the rheological behavior of cement pastes with micro- and nano-materials beyond the single-point testing customarily presented. An experimental program was developed to characterize and discuss the effects of microcrystalline cellulose (MCC) and nanofibrillated cellulose (NFC) on the rheological behavior of cement pastes. The investigation included both dynamic and static regimes, with a specific range of percentages of MCC and NFC. During the dynamic evaluation both MCC and NFC presence resulted in stiffer cement pastes, with increases in yield stress of up to 136% with 0.040% of NFC and 94% of MCC. MCC-specimens showed non-monotonic behavior regarding the static yield stress values. The rheological characteristics of the NFC gel itself affected the general behavior of the cement paste. The water present in the gel was found to be only partially available as mixing water.