Disease staging aims to measure the development of disease that uses clinical criteria to qualitatively classify the course of illness. Staging is a critical task in many clinical scenarios, for example, it could be used to guide the therapy and care, predict the clinical outcomes, optimize the utilization of resources, etc. Recently, data-driven disease staging using massive observational data has attracted significant attentions in literature. However, it is a technically challenging task not only because it is an unsupervised job without professional guidance as traditional ways do, but also it is crucial to generate clinically meaningful explanations in addition to stage prediction. In this work, we propose an interpretable deep learning framework, named Deep Staging, for data-driven explainable disease staging. The proposed approach could not only predict the disease stages based on observational medical data, but also generate clinically relevant characterizations of the disease stage outputs. Experiments on a real-world healthcare dataset demonstrate the effectiveness of the proposed framework.