Aminopeptidase N (APN)/CD13 as ubiquitously expressed membrane peptidase exerts important functions in diverse cellular processes, such as proliferation, migration and differentiation. Previously, a role of APN in the invasiveness of melanoma cells has been demonstrated, but the underlying molecular mechanisms controlling APN expression are not understood. The present study demonstrates that lack of APN expression in primary and established melanoma cells was directly associated with a high-grade DNA methylation status of the myeloid APN promoter. Demethylation by 5-aza-2'-desoxycytidine not only induced constitutive and cytokine-regulated APN protein expression but also resulted in an increased APN-dependent migration of melanoma cells. Furthermore, its heterogeneous expression was inversely correlated to the expression of melanocytic marker proteins in established as well as in short-term cultured human melanoma cells. Staining of tissue microarrays generated from a large series of melanoma samples and control tissues demonstrated a higher APN expression in primary melanoma lesions when compared with nevi and metastases, which was neither associated with clinico-pathological parameters nor with the patients' outcome. Thus, the heterogeneous APN expression pattern in melanoma cells is epigenetically controlled and directly associated with an altered migration capacity but not of clinical significance in our study group.