Oral epithelial dysplasia (OED) is a premalignant lesion of the oral mucosa. Considering the poor 5-year survival rate of oral cancer, further investigation is needed in order to determine the pathogenesis of OED. In the present study, serial analysis of gene expression (SAGE) data from patients with OED were compared to normal controls to identify differentially expressed genes (DEGs). SAGE data were obtained from the Gene Expression Omnibus, and included samples from patients with mild, moderate, or severe dysplasia. The DEGs were identified using the edgeR software package and functional-enrichment analysis was performed with the DAVID (https://david.ncifcrf.gov/) software program. The co-expression network was constructed using the CoExpress software and target genes of long non-coding RNAs (lncRNAs) were predicted according to the proximity between the lncRNAs and mRNAs in the genome. A total of 517 DEGs were identified, including 409 mRNAs and 108 lncRNAs. Functional-enrichment analysis showed that mRNAs and lncRNAs involved in epithelial cell differentiation, epithelium development, and epidermal cell differentiation were significantly enriched in the DEGs. Thirty-eight potential regulatory relationships were unveiled between lncRNAs and mRNAs, and two subnetworks were discovered by analyzing the topological properties of the co-expression network. In conclusion, we have identified key mRNAs and lncRNAs in OED, and these findings may aid in understanding the pathogenesis of OED and advance potential future treatments.