Proteus syndrome (PS) is a postnatal mosaic overgrowth disorder, progressive and disfiguring. It is clinically diagnosed according to the criteria reported by Biesecker et al. We describe the case of a 49-year-old woman who presented with a 10-year history of pauci-symptomatic infiltrating plaque lesions on the sole and lateral margin of the left foot, which had been diagnosed as a keloid. The patient had a positive history for advanced melanoma and a series of subtle clinical signs, such as asymmetric face, scoliosis, multiple lipomas on the trunk, linear verrucous epidermal nevi, and hyperpigmented macules with a mosaic distribution. Even if the clinical presentation was elusive, she had enough criteria to be diagnosed with PS. This case describes the first evidence, to the best of our knowledge, of pauci-symptomatic PS in adulthood, reports its rare association with advanced melanoma, and illustrates the importance of even minor cutaneous clinical signs, especially when atypical, in formulating the diagnosis of a complex cutaneous condition such as this.