A third to half of penile invasive squamous cell carcinomas are human papillomavirus (HPV) related. Warty (condylomatous), warty-basaloid, and basaloid carcinomas are the most common subtypes associated with HPV. Less frequent are clear cell and lymphoepithelioma-like carcinomas. Here we report a novel penile tumor associated with HPV. Twelve cases were selected from 1010 penile carcinomas, part of an international HPV detection study conducted at the Institut Català d’Oncologia, Barcelona, Spain. Immunostaining with p16INK4a was performed on all cases, and HPV-mRNA detection was also performed. En bloc full tumor staining was the utilized criteria for positivity of p16INK4a. For HPV-DNA detection, whole-tissue section polymerase chain reaction analysis was performed by SPF10-DEIA-LiPA25 (version 1). The patients’ ages ranged from 42 to 92 years (average, 71 y). The tumor was most commonly located in the glans. A characteristic microscopic finding was the presence of a moderate to dense tumor-associated inflammatory cell infiltrate composed of neutrophils, lymphocytes, plasma cells, or eosinophils. Tumors grew in large solid sheets, nests, or had a trabecular pattern. Cells were large and poorly differentiated or anaplastic. Keratinization was minimal or absent. Nuclei were large with prominent nucleoli. Mitoses were numerous. Tumor necrosis was common. Deep invasion of the corpora cavernosa was frequent. p16INK4a and HPV-DNA were positive in all cases, whereas mRNA detection was positive in 9 cases only. The prevalent genotype was HPV16 (9 cases, 75%). Other genotypes were HPVs 58, 33, and 66. Medullary carcinomas of the penis are morphologically distinctive HPV-related high-grade neoplasms affecting older individuals. More studies are necessary to delineate the epidemiological, clinical, and molecular features of this unusual penile neoplasm.