Poly-3-hydroxybutyrate (PHB) and bacterial cellulose (BC) are both natural polymeric materials that have the potential to replace traditional, nonrenewable polymers. In particular, the nanofibrillar form of bacterial cellulose makes it an effective reinforcement for PHB. Neat PHB, bacterial cellulose, and a composite of PHB/BC produced with 10 wt % cellulose were composted under accelerated aerobic test conditions, with biodegradability measured by the carbon dioxide evolution method, in conjunction with spectroscopic and diffraction methods to assess crystallinity changes during the biodegradation process. The PHB/BC composite biodegraded at a greater rate and extent than that of PHB alone, reaching 80% degradation after 30 days, whereas PHB did not reach this level of degradation until close to 50 days of composting. The relative crystallinity of PHB and PHB in the PHB/BC composite was found to increase in the initial weeks of degradation, with degradation occurring primarily in the amorphous region of the material and some recrystallization of the amorphous PHB. Small angle X-ray scattering indicates that the change in PHB crystallinity is accompanied by a change in morphology of semicrystalline lamellae. The increased rate of biodegradability suggests that these materials could be applicable to single-use applications and could rapidly biodegrade in compost on disposal.