Melanoma is one of the most aggressive forms of tumor, being responsible for about 80% of skin cancer deaths. Much effort is being directed at obtaining less-toxic anticancer therapies, and the combination between low cytotoxic doses of chemotherapeutic drugs and natural differentiative compounds seems to be of particular importance. The present study was undertaken to examine the possible role of a combination therapy using paclitaxel (PTX) as chemotherapeutic molecule and theophylline (TH) as differentiative agent in the prevention of metastasis in B16-F10 melanoma-bearing C57BL6/N mice. In vitro proliferation studies demonstrated that TH enhanced the antiproliferative effect of PTX. In the in vivo experiments, a highly sensitive computerized image analysis method, performed on histological lung sections of mice injected with melanoma cells, was used to quantify the efficacy of the treatments. This study demonstrated that the simultaneous treatment of mice with TH and a low dose of PTX produced a similar anti-invasive effect than that caused by highly toxic PTX concentration.