Perivascular epithelioid cell neoplasms (PEComas) are a family of mesenchymal tumors with features of both smooth muscle and melanocytic differentiation, with or without true melanin pigment. The highly variable morphology of PEComas results in a broad differential diagnosis that is also dependent on anatomic site. A subset demonstrates rearrangements involving the TFE3 (Xp11) locus, which can be used in diagnostically difficult cases. Here we describe a case of a melanotic PEComa with NONO-TFE3 fusion occurring in the sinonasal mucosa, as demonstrated by both next-generation sequencing and molecular cytogenetic studies. This case is the first of its kind in the literature and only the second documented PEComa harboring a NONO-TFE3 rearrangement. In light of unequivocal molecular ancillary studies, this case illustrates that PEComa must enter the differential for pigmented lesions of the sinonasal mucosa, where malignant melanoma would be much more likely to occur.