Fifty-one deep-water benthic species of Rhodophyta associated with the deep (> 30 m) fore-reef at Lee Stocking Island, Bahamas are reported. Including species described based on our collections from Lee Stocking Island, 25 of these species are first reports from the Bahamas archipelago. Peyssonnelia abyssica sp. nov. and Perikladosporon abaxiale sp. nov. are newly described. Peyssonnelia abyssica is characterized by having a thin crust (to 5 cells and to 75 μm thick vegetatively), hypothallial filaments in broad fan-shaped arrangements, perithallial cells cut off at right angles to the hypothallus with the proximal perithallial cell giving rise to two simple files of cells, and a rara-avis -type of nemathecium in which very large (to 150 μm in length and to 90 μm in diameter) tetrasporangia are produced. Perikladosporon abaxiale is nearly entirely prostrate and possesses regularly opposite and equal lateral branchlets which are principally abaxially developed. Perikladosporon abaxiale is also recognized from submersible collections in Puerto Rico.