The discovery, structure elucidation, and solid-phase synthesis of namalide, a marine natural product, are described. Namalide is a cyclic tetrapeptide; its macrocycle is formed by only three amino acids, with an exocyclic ureido phenylalanine moiety at its C-terminus. The absolute configuration of namalide was established, and analogs were generated through Fmoc-based solid phase peptide synthesis. We found that only natural namalide and not its analogs containing l-Lys or l-allo-Ile inhibited carboxypeptidase A at submicromolar concentrations. In parallel, an inverse virtual screening approach aimed at identifying protein targets of namalide selected carboxypeptidase A as the third highest scoring hit. Namalide represents a new anabaenopeptin-type scaffold, and its protease inhibitory activity demonstrates that the 13-membered macrolactam can exhibit similar activity as the more common hexapeptides.