The authors report a case of basaloid carcinoma involving the anus and rectum of a 57-year-old woman. Microscopically, the tumor showed unusual morphologic features strongly resembling a spiradenocylindroma because it consisted, in most parts, of basaloid cell nodules arranged in a jigsaw-puzzle fashion containing or surrounded by eosinophilic basal membrane material; in addition, there were intratumoral lymphocytes. The overlying squamous epithelium manifested dysplastic changes compatible with in situ squamous carcinoma that gradually became invasive and blended with basaloid cell islands; additionally, there were koilocytes in the squamous epithelium. A molecular biology study identified HPV-16 in the lesional tissue. Analysis of the CYLD gene did not prove any mutation.