Organic coatings are widely used to protect metals from corrosion in high-temperature marine environments. Compared with inorganic or metal coatings, organic coatings exhibit favorable properties, such as a reasonable cost, adequate flexibility, and easy fabrication. However, most organic coatings are limited to relatively short protection times and thus fail to meet the increasing demands for industrial applications. In this paper, graphene oxide (GO) was added to cyanate ester (CE) coatings as a corrosion inhibitive filler. Electrochemical analysis shows that a 3 wt % GO/CE coating has favorable corrosion protection properties with a low-frequency resistance higher than 106 Ω cm2 and a corrosion rate of 632.9 × 10–6 mm per year after 1320 h of immersion in a high-temperature marine environment. Top-view and cross-sectional SEM images identify the electrochemical results. Furthermore, chemical analyses by Fourier transform infrared spectroscopy and X-ray photoelectron spectroscopy demonstrate that hydroxyl groups of GO can react with cyanate groups, and therefore, a robust cross-linked structure was formed in the GO/CE coating. The synergistic effect of the physical shielding of GO and the robust cross-linked structure makes the GO/CE coating a promising choice for corrosion protection of steel in high-temperature marine environments. Our study also illustrates a novel method for preparing other chemically cross-linked composite coatings.