Cystic lesions located in the paravaginal region are rare. When present, paravaginal cysts are typically benign and are incidentally found on routine gynecological exams; however, rarely they can be malignant. Treatment options for paravaginal cancers are not well studied and early diagnosis may help improve prognosis in these patients. Our case describes a 55-year-old female with a recurrent paravaginal cyst that was remarkable for serous papillary adenocarcinoma despite biopsy and fluid cytology negative for malignancy. This case demonstrates that malignancy should be considered highly with a recurrent paravaginal cyst, especially when present over a short interval.