The present research investigated the effect of organosolv pretreatment on two species of salt-tolerant Salicornia spp. biomass, Salicornia dolichostachya and Salicornia ramosissima, for increasing biomethane production through anaerobic digestion. The final biomethane yield of de-juiced green fibers of Salicornia spp. from wet fractionation increased by 23–28% after organosolv treatment. The highest methane yield of about 300 mL-CH4/gVS was found after organosolv treatment with 60% v/v ethanol solution at 200 °C for 30 min, or at 180 °C for 30 or 60 min treatment time. Furthermore, the methane production rate increased significantly, reducing the time until 95% of the final methane yield was reached from 20 days to 6–10 days for the organosolv-treated biomass. This research shows that the process of anaerobic digestion of halophyte biomass benefits from cascade processing of Salicornia fibers in a biorefinery framework by sequential wet and organosolv fractionation for full utilization of halophytic biomass.