Tryptase is a protease released from mast cells and is believed to contribute to the inflammatory process in allergic diseases including asthma. In the course of screening to find tryptase inhibitors, we isolated two new tryptase inhibitors, cyclotheonamide E4 (3) and E5 (4), from a marine sponge of the genus Ircinia. The structures of these molecules were determined by interpretation of 1H and 13C NMR spectra, and they were shown to be closely related to the previously reported cyclotheonamides E (1), E2, and E3 (2). These molecules contain two unusual amino acids, vinylogous tyrosine and alpha-ketohomoarginine, which are involved in strong activities against serine proteases. Cyclotheonamide E4 showed potent inhibitory activity against human tryptase (IC50 5.1 nM). Therefore, cyclotheonamide E4 may be useful as a therapeutic agent in the treatment of allergic diseases including asthma.