Autophagy is a self-eating pathway for maintaining normal cellular physiology, while dysregulation of autophagy is associated with cancer progression. Autophagy-related 4B gene (ATG4B) is a cysteine protease to regulate autophagosome formation and is positively correlated with poor prognosis of colorectal cancer (CRC) patients. An increasing number of reports have implied that ATG4B might be an attractive drug target for CRC. Natural products are the most important source of drug development for cancer therapy due to their high degree of diversity in chemical structure. However, there are few natural products targeting autophagy regulation, especially targeting ATG4B. We aim to identify effective natural compounds from costal plants against ATG4B as potential CRC therapies. We extracted the whole plants, stem, and leaves from nine coastal plant species of Taiwan using different solvents including acetone, methanol, or chloroform. We then evaluated their effects on ATG4B activity and cancer malignancy in CRC cells (DLD-1, HCT116, and SW620). Among these 26 extracts, we found that the methanol leaf extract of A. elliptifolia significantly inhibited ATG4B proteolytic activity. Moreover, cell viability and colony formation and mobility were decreased in CRC cells treated with the extract. The extract further reduced the number of living cells and induced subG