This study aims to explore—from the perspectives of the employees at the Information Technology Department of the Ministry of Interior in the Sultanate of Oman—the extent to which digital leadership, continuous improvement, and other factors achieve organizational excellence in addition to revealing the factors that enhance the organization’s perception. The study is based on the assumption that different factors contribute to improving the organization’s excellence. Methodology: A pragmatic philosophy underpins the research design. A mixed methods case study approach involving surveys administered to 40 male and female employees at the case organization was used for data collection. The survey includes four open-ended questions to identify viable quotes that validate quantitative results. Descriptive statistics is used for data analysis of the quantitative component. Findings: The findings suggest that digital leadership, continuous improvement, communication, training, learning and innovation, and achieving digital excellence improve organizational performance and excellence. Meaningfully, although the sample is taken from one case study in a limited geographical area in Oman, which may risk the generalizability of the findings, the study opens a new prospect of research in the field of organizational excellence. Recommendation: the ministry can enhance excellence when implementing digital transformation by adopting artificial intelligence (AI), the Internet of Things (IoT), and blockchain. By adopting these three technologies, the ministry can improve its operations, increase security and transparency, and provide more advanced services to the public.