This research evaluates four sustainable cementitious composites with sustainable plant fibers and bio-aggregates: (1) cementitious matrix composite with lechuguilla fibers (LFC) and (2) with flax fibers (FFC); and (3) cementitious matrix composite with wood shavings (WSC) and (4) with hemp shavings (HSC). The fibers are for reinforcement and the shavings act as bio-aggregates as a total replacement for limestone aggregates. The lechuguilla (LF) and flax (FF) fibers were treated; wood (WS) and hemp (HS) bio-aggregates were also processed. Nineteen mixtures were manufactured, and five were used as controls, and the hygrothermal, mechanical, and durability properties were evaluated. The results for LFC and FFC showed that fiber treatment negatively affected flexural–compressive strength; untreated LFC with accelerated deterioration had better mechanical behavior, higher density, and lower porosity than FFC. Strength and density decreased, but porosity increased with increasing fiber volume (Vf). Regarding WSC and HSC, the microstructure of WS and HS had a significant effect on the physical and mechanical properties. The high porosity influenced the results obtained, since it decreased compressive strength and bulk density; however, thermal conductivity, hygroscopicity, and vapor resistance showed better behavior in most cases than the control specimens, i.e., without bio-aggregates.