In brown algae (Phaeophyceae), only a few taxa are reported to have plastids containing pyrenoids and this character has often been used for systematic delineation. Members of the Ectocarpales display large, stalked and exserted pyrenoids in their plastids, whereas the Scytothamnales, as well as the genera Asterocladon, Asteronema and Bachelotia, exhibit plastids arranged in a stellate configuration with pyrenoids embedded in the plastid stroma. The evolution of plastid characters has remained difficult to establish, especially because of a persistent lack of resolution in brown algal molecular phylogenies. Here, we generated a seven-locus dataset for a species-rich taxon sampling, to reassess phylogenetic relationships of pyrenoid-bearing brown algal taxa. Within the Ectocarpales, the relationships among families are clarified. The minute chordariacean genus Herponema is assigned to the family Acinetosporaceae. The systematic positions of two enigmatic genera are revised: Chordariopsis is assigned to the Adenocystaceae, and Spongonema is transferred back to the Ectocarpaceae. The new order Asterocladales, which is sister to the Ectocarpales, is proposed to accommodate species of the genus Asterocladon. The order Scytothamnales is shown to include the genus Bachelotia in a new family Bachelotiaceae, as well as another new family Asteronemataceae, accommodating the genus Asteronema. These new taxonomic insights also shed light on the evolution of plastid morphology and arrangement in brown algae. Stellate plastid configurations have evolved independently in Asterocladales and Scytothamnales. Evolutionary scenarios underlying the diversity of stellate configurations in the Scytothamnales and the Asterocladales–Ectocarpales lineage are discussed.