Gingiva hyperpigmentation resulting from physiological melanosis causes aesthetic discomfort and is usually perceived as a disease by patients because healthy attached gingiva is typically characterized by coral pink coloring with stippling and scalloped contours. When physiological melanosis compromises the aesthetics of smiling, it may induce insecurity in patients, who usually seek out alternatives for reducing or eliminating hyperpigmentation. We present a case report of a surgical procedure combining gingivectomy with gingivoplasty for the management of physiological melanosis. The surgical procedure was performed on a 40-year-old female patient with bilateral pigmentation in both arches. The results of the histological analysis confirm the diagnoses of melanotic macula, with papillary hyperplasia and cytopathic changes being suggestive of HPV infection, which was verified using an immunohistochemistry analysis based on the detection of a major capsid protein of HPV. Acceptable functional and aesthetic results were obtained for the patient without major discomfort during the postoperative period. In cases when HPV infection is present, long-term follow-up becomes necessary.