Systematic molecular studies have not been performed on ecologically important brown algae (Sargassum) in the Gulf of California, Mexico, where 42 specific and infraspecific names have been recorded within this genus. We conducted phylogenetic analyses of nuclear ribosomal ITS and mitochondrial cox1 and cox3 sequences, along with detailed morphological observations of Sargassum collected in the Gulf of California. We confirmed the presence of six species, five previously described—S. herporhizum, S. horridum, S. johnstonii, S. lapazeanum, and S. sinicola, as well as the newly described Sargassum ulixei sp. nov. which is characterized by terete primary axes arising from the stipe, lanceolate to elliptical sessile ecostate blades with smooth margins, cryptostomata, ellipsoidal vesicles with a short mucron, and cylindrical to ellipsoidal receptacles. The individual analyses and subsequent phylogenetic analysis recognized two groups previously described by Dawson, one as Sargassum and other as Horridum. Our studies suggest that the Gulf of California is a region with endemic Sargassum species, and is clearly distinguished from the Pacific side of Baja California, where recently introduced species are common. Based on phylogenetic relationships, we propose two geographical origins for the Sargassum from the Gulf of California: a first group originating from the proto-Gulf, related to species from the northern hemisphere (including five species); and a second group, containing S. sinicola, introduced when the southern end opened at a later stage.