This paper provides descriptions of two new species of Calcigorgia gorgonians collected from the Sea of Okhotsk between 1973 and 2008. The new species are Calcigorgia herba sp. nov. and С. lukini sp. nov., belonging to the deep-water coral fauna of the temperate Northern Pacific. The taxonomy structure of the genus is reviewed and a comparative table is provided for all known species of Calcigorgia. The following taxonomic changes are made: the diagnosis of the genus was corrected from that given in Matsumoto et al. (2019); synonymization of C. simushiri Dautova, 2018 with C. spiculifera Broch, 1935 and inclusion of additional specimens in C. japonica Dautova, 2007 (both performed by Matsumoto et al. 2019) are assumed erroneous. The finding of previously undescribed species emphasizes the need for further surveys, particularly in deeper waters, to improve knowledge of the Octocorallia fauna in Far East seas. The distribution of Calcigorgia (Octocorallia, Acanthogorgiidae) is reviewed and presented based on field and collection studies published since 1935 as well as miscellaneous data from previous literature.