Malignant melanoma (MM) urgently needs identification of new markers with better predictive value than currently-used clinical and histological parameters. Cancer cells stimulate the formation of a specialized tumor microenvironment, which reciprocally affects uncontrolled proliferation and migration. However, this microenvironment is heterogeneous with different sub-compartments defined by their access to oxygen and nutrients. This study evaluated microvascular density (MVD), CD3+ lymphocytes (TILs) and FOXP3+ T-regulatory lymphocytes (Tregs) on formalin-fixed paraffin-embedded tissue sections using light microscopy. We analyzed 82 malignant melanomas, divided according to the AJCC TNM classification into four groups--pT1 (35), pT2 (17), pT3 (18) and pT4 (12)--and 25 benign pigmented nevi. All parameters were measured in both the central areas of tumors (C) and at their periphery (P). A marked increase in all parameters was found in melanomas compared to nevi (p = 0.0001). There was a positive correlation between MVD, TILs, FOXP3+ Tregs and the vertical growth phase. The results show that MVD, TILs and FOXP3+ Tregs substantially influence cutaneous melanoma microenvironment. We found significant topographic differences of the parameters between central areas of tumors and their boundaries.