Different amounts of cellulose nanocrystals (CNCs) were added to glycerol-plasticized thermoplastic starch (TPS) to obtain bio-based nanocomposites. First, nanocomposites are prepared by extrusion and their structure is studied at different scales using WAXS (Wide Angle X-ray Scattering) and solid-state NMR (Nuclear Magnetic Resonance) for local/crystalline organization, AF4 (Asymmetrical Flow Field-Flow Fractionation) for molecular weight and chain length, and SEM (Scanning Electron Microscopy) for the morphology at a larger scale. Then, relevant mechanical properties and behavior in physiological conditions (swelling, enzymatic degradation) are characterized. The results show that the incorporation of cellulose nanocrystals up to 2.5 wt% causes a mechanical reinforcement as determined by DMTA (Dynamic Mechanical Thermal Analysis) and reduces the swelling and the enzymatic degradation of the materials compared to reference TPS. This could be linked to the formation of starch-cellulose hydrogen and hydroxyl bonds. Conversely, above 5 wt% CNC content nanocrystals seem to aggregate which in turn worsens the behavior in physiological conditions.