This study presents the fabrication and characterization of hierarchical fiber-reinforced biodegradable composites (HFBCs) based on poly(3-hydroxybutyrate-co-4-hydroxybutyrate) (PHA). A dual-scale reinforcement strategy was adopted by simultaneously incorporating natural cotton woven fabrics (CWFs) and TEMPO-oxidized cellulose nanofibers (TCNFs), enabling macroscopic load-bearing and microscopic stress transfer. To improve interfacial compatibility between CWFs and TCNFs and promote the dispersion of aggregated TCNFs, a novel poly(lactic acid)-based heterocyclic compatibilizer (LHC) was synthesized and complexed with TCNFs. CWFs were coated with an PHA/LHC-modified TCNF solution and thermally treated to form an integrated hierarchical structure. The resulting HFBCs achieved a 582% increase in Young’s modulus and a 157% increase in tensile strength compared to neat PHA. The reinforcing mechanism was also proposed based on molecular simulations and spectroscopic analysis.