Functionalized cellulose nanocrystals (PHCNs) were synthesized by grafting poly(3-hydroxybutyrate-co-3-hydroxyvalerate) (PHBV) onto cellulose nanocrystals (CNCs). The resultant PHCNs with high loading levels were uniformly dispersed into a PHBV matrix to produce fully biodegradable nanocomposites, which showed superior mechanical performance and thermal stability. Compared with those of neat PHBV, the tensile strength, Young’s modulus, and elongation at break of the nanocomposites with 20 wt % PHCNs were enhanced by 113%, 95%, and 17%, respectively. Meanwhile, the initial decomposition temperature (T0), temperature at 5% weight loss (T5%), maximum decomposition temperature (Tmax), and complete decomposition temperature (Tf) increased by 29.6, 23.9, 34.7, and 37.0 °C, respectively. This improvement was primarily ascribed to uniform dispersion of the PHCNs and to strong interfacial adhesion between filler and matrix due to the chain entanglements, cocrystallization, and hydrogen bonding interactions. Moreover, the nanocomposites showed a wider melt-processing window than neat PHBV. Furthermore, the crystallinity and hydrophilic properties of the nanocomposites could be modulated through with the increase of the PHCN contents. In addition, the nanocomposites were nontoxic to human MG-63 cells. Such high performance bionanocomposites have great potential in expanding the utilization of CNCs from natural resources and practical application as PHBV-based bioplastic and biomedical materials.