Alcyonaria species are among the important marine invertebrate classes that produce a wealth of chemically diverse bioactive diterpenes. Examples of these are the potent microtubule disruptor sarcodictyins and eleutherobin. The genus Cladiella has proven to be a rich source of cytotoxic eunicellin-based diterpenoids. Five new eunicellin diterpenes, pachycladins A-E (1-5), were isolated from the Red Sea soft coral Cladiella pachyclados. The known sclerophytin A Cladiellisin, 3-acetylcladiellisin, 3,6-diacetylcladiellisin, (+)-polyanthelin A, klysimplexin G, klysimplexin E, sclerophytin F methyl ether, (6Z)-cladiellin (cladiella-6Z,11(17)-dien-3-ol), sclerophytin B, and patagonicol were also identified. The structures of the isolated compounds were elucidated by extensive interpretation of their spectroscopic data. These compounds were evaluated for their ability to inhibit growth, proliferation, invasion, and migration of the prostate cancer cells PC-3. Some of the new metabolites exhibited significant anti-invasive activity.