Medium chain-length polyhydroxyalkanoates (mPHAs) are flexible elastomeric biopolymers with valuable properties for biomedical applications like artificial arteries and other medical implants. However, an environmentally friendly and high productivity process together with the tuning of the mechanical and biological properties of mPHAs are mandatory for this purpose. Here, for the first time, a melt processing technique was applied for the preparation of bionanocomposites starting from poly(3-hydroxyoctanoate) (PHO) and bacterial cellulose nanofibers (BC). The incorporation of only 3 wt % BC in PHO improved its thermal stability with 25 °C and reinforced it, increasing the Young's modulus with 76% and the tensile strength with 44%. The percolation threshold calculated with the aspect ratio of the fibers after melt processing was very low and close to 3 wt %. We showed that this bionanocomposite is able to preserve the ductile behavior during storage, no important aging being noted between 3 h and one month after compression-molding. Moreover, this study is the first to investigate the melt processability of PHO nanocomposite for tube extrusion. In addition, biocompatibility study showed no proinflammatory immune response and better cell adhesion for PHO/BC nanocomposite with 3 wt % BC and demonstrated the high feasibility of this bionanocomposite for in vivo application of tissue-engineered blood vessels.