A 55 year old HIV positive male had a skin lesion biopsy which showed atypical vascular proliferation within the superficial and deep dermis with mild atypia of lining endothelial cells. A sparse lymphoplasmacytic infiltrate surrounding the irregular vascular channels was noted. Immunohistochemistry highlighted the atypical blood vessels with the vascular markers CD31, CD34 and Factor VIII. The differential diagnosis included unusual vascular or lymphatic proliferations, stasis dermatitis, kaposiform hemangioendothelioma, progressive lymphangioma and angiosarcoma with focal Kaposi's sarcoma features. Characteristic human herpes virus-8 positive staining helped support the diagnosis of patch stage of Kaposi's sarcoma. Herein, we discuss the case findings, differential diagnosis and characteristic histological findings associated with the patch stage of Kaposi's sarcoma which can be an elusive diagnosis.