Knowledge on distribution of coralligenous communities with gorgonian facies (Anthozoa: Gorgonacea) is still rather poor in the Eastern Mediterranean Sea. This is mainly due to their considerably deeper distribution than their Western basin counterparts. In the framework of “Nautilos” Project (2005-2008) several combined Submersible and ROV surveys were conducted to systematically locate gorgonian facies and visually assess their basic structure and distribution. Gorgonian assemblages were recorded from 10 study sites within a depth range of 30-120m. Shallow gorgonian assemblages were an exception, with most found at depths greater than 50m. In general, Eunicella cavolinii and Paramuricea clavata were found to be the most common species, while Leptogorgia sarmentosa, Eunicella singularis and Corallium rubrum were extremely rare findings. Considering the susceptibility of these habitats to various anthropogenic impacts, this is an important first attempt to map their spatial distribution and give a general description of their composition and present ecological state.