In order to produce sustainable, bio-based and highly biodegradable materials, composites based on poly(hydroxybutyrate-co-hydroxyvalerate) (PHBV) and fibers of Posidonia oceanica (PO), a dominant Mediterranean seagrass, were produced by simple melt mixing and characterized in terms of thermal stability, morphology and rheological/mechanical properties. In view of their potential application in marine environments, degradation of the developed composites was evaluated under simulated and real marine environmental conditions for 1 year. Using 10 wt % of acetyl tributyl citrate (ATBC) as a plasticizer, smooth processing was achieved for up to 30 wt % of PO fibers, despite the reduction of the melt fluidity observed with increasing fiber loading. The tensile modulus slightly increased (from 2 to 2.4 GPa) while the tensile strength and the elongation decreased (from 23.6 to 21.5 MPa and from 3.2 to 1.9%, respectively) by increasing the PO fiber content from 0 to 30 wt %. Interestingly, the impact resistance of the composites increased with the increasing of the PO content: the Charpy&rsquo;s impact energy increased from 3.6 (without fiber) to 4.4 kJ/m2 for the composite with 30 wt %. The results of the aerobic biodegradation under simulated marine conditions showed that the presence of PO fibers favored the physical disintegration of the composite increasing the biodegradation rate of the polymeric matrix: after 216 days, the composite with 20 wt % PO fibers showed a biodegradability of about 30% compared to 20% of the composite without fibers. Under real marine conditions, the specimens containing PO fibers showed higher weight losses and deterioration of tensile properties compared to those without fibers. Presumably, biodegradation occurred after colonization of the specimen, and the specimens with 20 wt % PO fibers showed well-developed biofilm consisting of bacteria and fungi on the surface after only 3 months of incubation in marine sediments, unlike the no-fiber specimens. Consequently, the persistence of an adequate mechanical performance for a relatively long period (1 year), due to a moderate rate of biodegradation in the marine environment, make the developed PHBV/PO composites particularly suitable for the production of relatively low-cost and biodegradable items which are usable in the sea and/or sand dunes, increasing the market opportunities for biopolymers such as PHBV and, at the same time, finding an eco-sustainable valorization for the PO fibrous residues accumulated in large quantities on Mediterranean beaches, which represents a problem for coastal municipalities.