Computational analysis on altered micro-nano-textural attributes of the oral mucosa may provide precise diagnostic information about oral potentially malignant disorders (OPMDs) instead of an existing handful of qualitative reports. This study evaluated micro-nano-textural features of oral epithelium from scanning electron microscopic (SEM) images and the sub-epithelial connective tissue from light microscopic (LM) and atomic force microscopic (AFM) images for normal and OPMD (namely oral sub-mucous fibrosis, i.e., OSF). Objective textural descriptors, namely discrete wavelet transform, gray-level co-occurrence matrix (GLCM), and local binary pattern (LBP), were extracted and fed to standard classifiers. Best classification accuracy of 87.28 and 93.21%; sensitivity of 93 and 96%; specificity of 80 and 91% were achieved, respectively, for SEM and AFM. In the study groups, SEM analysis showed a significant (p < 0.01) variation for all the considered textural descriptors, while for AFM, a remarkable alteration (p < 0.01) was only found in GLCM and LBP. Interestingly, sub-epithelial collagen nanoscale and microscale textural information from AFM and LM images, respectively, were complementary, namely microlevel contrast was more in normal (0.251) than OSF (0.193), while nanolevel contrast was more in OSF (0.283) than normal (0.204). This work, thus, illustrated differential micro-nano-textural attributes for oral epithelium and sub-epithelium to distinguish OPMD precisely and may be contributory in early cancer diagnostics.