The E6 protein from high-risk human papillomavirus types interacts with and degrades several PDZ domain-containing proteins that localize to adherens junctions or tight junctions in polarized epithelial cells. We have identified the tight junction-associated multi-PDZ protein PATJ (PALS1-associated TJ protein) as a novel binding partner and degradation target of high-risk types 16 and 18 E6. PATJ functions in the assembly of the evolutionarily conserved CRB-PALS1-PATJ and Par6-aPKC-Par3 complexes and is critical for the formation of tight junctions in polarized cells. The ability of type 18 E6 full-length to bind to, and the subsequent degradation of, PATJ is dependent on its C-terminal PDZ binding motif. We demonstrate that the spliced 18 E6* protein, which lacks a C-terminal PDZ binding motif, associates with and degrades PATJ independently of full-length 18 E6. Thus, PATJ is the first binding partner that is degraded in response to both isoforms of 18 E6. The ability of E6 to utilize a non-E6AP ubiquitin ligase for the degradation of several PDZ binding partners has been suggested. We also demonstrate that 18 E6-mediated degradation of PATJ is not inhibited in cells where E6AP is silenced by shRNA. This suggests that the E6-E6AP complex is not required for the degradation of this protein target.