Lymphomatoid papulosis (LyP) is defined as a recurrent self-healing papulonodular eruption with the histological features of a (CD30+) cutaneous T-cell lymphoma. The atypical cells usually have a CD3+/-, CD4+/-, CD8-, CD30+, CD56- T-cell phenotype. We report an unusual case of LyP, in which the atypical cells expressed a CD3-, CD4-, CD8-, CD30+, CD56+ phenotype. Detailed phenotypic and genotypic analysis confirmed that these cells had a natural killer (NK)-cell phenotype. Lymphomas with an NK-cell phenotype usually have a poor prognosis. However, the waxing and waning of papular lesions for more than 20 years and the excellent response to low-dose oral methotrexate in this patient suggest similar clinical behaviour to LyP cases with a T-cell phenotype.