Cell-free microRNA (miRNA) in biofluids released by tumors in either protein or vesicle-bound form, represent promising minimally-invasive cancer biomarkers. However, a highly abundant non-tumor background in human plasma and serum complicates the discovery and detection of tumor-selective circulating miRNAs. We performed small RNA sequencing on serum and plasma RNA from Nasopharyngeal Carcinoma (NPC) patients. Collectively, Epstein Barr virus-encoded miRNAs, more so than endogenous miRNAs, signify presence of NPC. However, RNAseq-based EBV miRNA profiles differ between NPC patients, suggesting inter-tumor heterogeneity or divergent secretory characteristics. We determined with sensitive qRT-PCR assays that EBV miRNAs BART7-3p, BART9-3p and BART13-3p are actively secreted by C666.1 NPC cells bound to extracellular vesicles (EVs) and soluble ribonucleoprotein complexes. Importantly, these miRNAs are expressed in all primary NPC tumor biopsies and readily detected in nasopharyngeal brushings from both early and late-stage NPC patients. Increased levels of BART7-3p, BART9-3p and particularly BART13-3p, distinguish NPC patient sera from healthy controls. Receiver operating characteristic curve analysis using sera from endemic NPC patients, other head and neck cancers and individuals with asymptomatic EBV-infections reveals a superior diagnostic performance of EBV miRNAs over anti-EBNA1 IgA serology and EBV-DNA load (AUC 0.87–0.96 vs 0.86 and 0.66 respectively). The high specificity of circulating EBV-BART13-3p (97%) for NPC detection is in agreement with active secretion from NPC tumor cells. We conclude EV-bound BART13-3p in circulation is a promising, NPC-selective, biomarker that should be considered as part of a screening strategy to identify NPC in endemic regions.