Cross-linked elastomers are stretchable materials that typically are not recyclable or biodegradable. Medium-chain-length polyhydroxyalkanoates (mcl-PHAs) are soft and ductile, making these bio-based polymers good candidates for biodegradable elastomers. Elasticity is commonly imparted by a cross-linked network structure, and covalent adaptable networks have emerged as a solution to prepare recyclable thermosets via triggered rearrangement of dynamic covalent bonds. Here, we develop biodegradable and recyclable elastomers by chemically installing the covalent adaptable network within biologically produced mcl-PHAs. Specifically, an engineered strain of Pseudomonas putida was used to produce mcl-PHAs containing pendent terminal alkenes as chemical handles for postfunctionalization. Thiol-ene chemistry was used to incorporate boronic ester (BE) cross-links, resulting in PHA-based vitrimers. mcl-PHAs cross-linked with BE at low density (<6 mole %) affords a soft, elastomeric material that demonstrates thermal reprocessability, biodegradability, and denetworking at end of life. The mechanical properties show potential for applications including adhesives and soft, biodegradable robotics and electronics.