Marine microorganisms have proven to be a rich source of structurally novel and biologically active compounds which might be useful for the development of new pharmaceutical agents. In our search for bioactive compounds from marine microorganisms, we have examined extracts of symbiotic bacteria associated with various marine invertebrates and isolated a new cytotoxic alkaloid, alteramide A (1), from the cultured mycelium of a bacterium Alteromonas sp. separated from the marine sponge Halichondria okadai. The mycelium was extracted with CHCl3/MeOH (2:1) and purified by Sephadex LH-20 column and Sep-Pak ODS cartridge. The molecular formula of 1 was determined as C26H38N2O6 by HRFABMS. UV absorption at λmax 347 nm (ε 11000) indicated extended π conjugation; IR spectrum showed presence of NH/OH (3400 cm−1) and unsaturated carbonyls (1680, 1610 cm−1); 13C NMR data suggested a tetramic acid. Detailed 1H-1H COSY, HMBC, NOE, and ROESY analyses revealed 1's structure including a bicyclo[3.3.0]octane unit, a five-membered ring system, and a tetramic acid moiety. The absolute stereochemistry at C-23 and C-25 was established as L-erythro configuration via chiral HPLC analysis of B-hydroxyornithine derived from ozonolysis of 1. Alteramide A (1) is a new macrocyclic lactam with a dienone and a dienoyltetramic acid, which undergoes intramolecular photochemical [4 + 4] cycloaddition to generate the hexacyclic derivative 2. Alteramide A (1) exhibited cytotoxicity against murine leukemia P388 cells (IC50 0.1 μg/mL), murine lymphoma L1210 cells (IC50 1.7 μg/mL), and human epidermoid carcinoma KB cells (IC50 5.0 μg/mL) in vitro, while compound 2 showed no cytotoxicity. This study describes the isolation, structure elucidation, and biological activity of alteramide A from a marine bacterium symbiotically associated with the sponge Halichondria okadai.