Oxygenated block polymers, comprising esters and carbonates, are priority materials to replace petrochemical polymers in a circular plastics economy. These materials should repopulate the thermomechanical property space mapped by current plastics and elastomers. Here, a novel machine learning approach, PolyReco, predicts structures of oxygenated block polymers meeting the mechanical performance thresholds for widely used and hard-to-replace petroleum derived hydrocarbon polymers. Triblock oxygenated polymers are represented as graphs, and a link prediction algorithm enables feature extraction to identify new block polymer combinations, and associated degrees of polymerization, to meet the target properties. PolyReco is paired with a visualization tool for further material down selection based on user requirements. Three case studies highlight and experimentally validate its predictive power for identifying high-performance oxygenated block polymers, with new block polymers prepared and tested. These new block polymers exhibit tensile mechanical properties in the range of high-impact polystyrene, poly(dimethylsiloxane), and styrenic elastomers; the experimental results indicate that PolyReco may help support the identification of sustainable materials that could reduce dependence on fossil-based polymer incumbents.