Poly(3-hydroxybutyrate) (PHB) is one of the most promising substitutes for the petroleum-based polymers used in the packaging and biomedical fields due to its biodegradability, biocompatibility, good stiffness, and strength, along with its good gas-barrier properties. One route to overcome some of the PHB’s weaknesses, such as its slow crystallization, brittleness, modest thermal stability, and low melt strength is the addition of cellulose nanocrystals (CNCs) and the production of PHB/CNCs nanocomposites. Choosing the adequate processing technology for the fabrication of the PHB/CNCs nanocomposites and a suitable surface treatment for the CNCs are key factors in obtaining a good interfacial adhesion, superior thermal stability, and mechanical performances for the resulting nanocomposites. The information provided in this review related to the preparation routes, thermal, mechanical, and barrier properties of the PHB/CNCs nanocomposites may represent a starting point in finding new strategies to reduce the manufacturing costs or to design better technological solutions for the production of these materials at industrial scale. It is outlined in this review that the use of low-value biomass resources in the obtaining of both PHB and CNCs might be a safe track for a circular and bio-based economy. Undoubtedly, the PHB/CNCs nanocomposites will be an important part of a greener future in terms of successful replacement of the conventional plastic materials in many engineering and biomedical applications.