Cancer is a serious health burden on global societies. The discovery and development of new anti-cancer therapies remains a challenging objective. Although it has been shown that lichen secondary metabolites may be potent sources for new anti-cancer agents, the Indonesian-grown folious lichens, Physcia millegrana, Parmelia dilatata and Parmeila aurulenta, have not yet been explored. In this study exhaustive preparative high-performance liquid chromatography was employed to isolate the lichen constituents with spectroscopic and spectrometric protocols identifying nine depsides 9–17, including the new methyl 4-formyl-2,3-dihydroxy-6-methylbenzoate 13. The cytotoxicity of the depsides towards cancer cells was assessed using the 3-(4,5-dimethylthiazol-2-yl)-2,5-diphenyltetrazolium bromide (MTT) assay. The results indicated lowest toxicity of the depsides towards human A549 lung cancer cells. Importantly, the di-depsides (11, 12 and 17) showed greatest toxicity, indicating that these structures are biologically more active than the mono-depsides against the HepG2 liver cancer, A549 lung cancer and HL-60 leukemia cell lines.