Coastal vegetated ecosystems are intense global carbon (C) sinks; however, seagrasses and mangroves in the Central Red Sea are depleted in organic C (Corg). Here, we tested whether Corg depletion prevails along the Red Sea, or if sediment Corg and nitrogen (N) stocks reflect the latitudinal productivity gradient of the Red Sea. We assessed Corg and N concentrations, stocks, isotopic compositions (δ13C and δ15N), and the potential contribution of primary producers to the organic matter accumulation in seagrass and mangrove sediments along the Eastern coast of the Red Sea. Sediment Corg concentration was higher in mangroves than seagrasses, while N concentrations were similar, resulting in higher C/N ratios in mangrove than seagrass sediments. Mangrove Corg stocks (integrated over the top 10 cm) were twofold higher than those of seagrasses. N concentrations and stocks decreased from south to north in seagrass sediments matching the productivity gradient while Corg concentrations and stocks were uniform. The δ15N decreased from south to north in seagrass and mangrove sediments, reflecting a shift from nitrate and nitrite as N sources in the south, to N2 fixation toward the north. Stable isotope mixing models showed that seagrass leaves and macroalgae blades were the major contributors to the organic matter accumulation in seagrass sediments; while mangrove leaves were the major contributors in mangrove sediments. Overall, vegetated sediments in the Red Sea tend to be carbonate-rich and depleted in Corg and N, compared to coastal habitats elsewhere. Specifically, mean Corg stocks in Red Sea seagrass and mangrove sediments (7.2 ± 0.4 and 14.5 ± 1.4 Mg C ha-1, respectively) are lower than previously reported mean global values. This new information of Blue Carbon resources in the Red Sea provides a background for Blue Carbon programs in the region while also helping to balance global estimates.