Dehydrodieugenol B and five related natural neolignans were isolated from the Brazilian plant species Nectandra leucantha. Three of these compounds were shown to be active against murine (B16F10) and human (A2058) melanoma cells but non-toxic to human fibroblasts (T75). These results stimulated the preparation of a series of 23 semi-synthetic derivatives in order to explore structure-activity relationships and study the biological potential of these derivatives against B16F10 and A2058 cell lines. These structurally-related neolignan derivatives were analyzed by multivariate statistics and machine learning, which indicated that the most important characteristics were related to their three-dimensional structure and, mainly, to the substituents on the neolignan skeleton. The results suggested that the presence of hydroxyl or alkoxyl groups at positions 3, 4 and 5 (with appropriate sidechains) promoted an increase in electropological and charge density, which seem to be important for biological activity against murine (B16F10) and human (A2058) melanoma cells.