The application of natamycin as a natural fungicide in edible coatings is challenging because of its low aqueous solubility. In this study, the natamycin/methyl-β-cyclodextrin (N/ME-β-CD) inclusion complex was fabricated and incorporated into waxy corn starch-based coatings for postharvest treatments. The phase solubility of natamycin in the presence of ME-β-CD at 293.2 K, 303.2 K, and 313.2 K is determined and used to calculate the process thermodynamic parameters. The N/ME-β-CD inclusion complex was confirmed and characterized by FTIR and 1H NMR spectroscopy. The results indicated that the inclusion complex was formed and the hydrophobic part (C16-C26) of natamycin might be partially inserted into the cavity of ME-β-CD form the wide rim. The effects of N/ME-β-CD incorporated starch-based coatings (N/ME-β-CD S coatings) on postharvest treatments of cherry tomatoes were evaluated in vivo. The N/ME-β-CD S coatings could reduce weight loss, delay fruit ripening, and inhibit fruit decay caused by Botrytis cinerea in tomato fruit during storage.