The advances of genomic sequence analyses and genome mining tools have enabled the exploration of untapped microbial natural products. Through genome mining studies to discover cryptic natural products, we found biosynthetic genes encoding a new lasso peptide in the genome sequence of a soil bacterium, Streptomyces sp. KCB13F003 isolated from Ulleung Island (a small volcanic island), Korea. The production and purification of the encoded peptide, named ulleungdin, were achieved by optimizing the culture conditions followed by LC-MS-targeted isolation. Structure elucidation was performed by NMR spectroscopic and MS spectrometric analyses and chemical means (Marfey's and GITC derivatizations), proving ulleungdin to be a new 15-mer class II lasso peptide with a threaded structure. Biological evaluation with the cell invasion assay and time-lapse cell tracking analysis revealed that ulleungdin has significant inhibitory activities against cancer cell invasion and migration.