Nineteen of the 31 octocoral species (61%) known from the Aleutian Islands belong to family Primnoidae, which form large deep-water (9-2,514 m) colonies providing habitat for one of the most productive fisheries in the North Pacific. These 19 species are described or redescribed and figured unless recent descriptions have been published. Eight new species are described, two in the genus Thouarella and six in the genus Plumarella. These two genera are redefined and differentiated by emphasizing the nature (keeled or not) of the inner side of their marginal scales and the inner side's articulation or lack thereof with the outer surface of the underlying opercular scales. Dicholaphis is proposed as a new subgeneric rank of the genus Plumarella, characterized by having polyps arranged on all sides of its branchlets, not on alternate opposite sides. A key is provided for the eight species of Aleutian Plumarella, and all 35 valid species in the genus are listed, including three new combinations: P. superba, P. abietina, and P. recta. A history of the Aleutian primnoids is recounted. Six primnoid species are reported from the Bering Sea, all of which also occur in the Aleutian Islands. Two-thirds of the Aleutian-Bering Sea primnoids are endemic to this region.