Purpose: Supply and demand characteristics, influenced by the pre- and post-oil economy of Oman, have caused unemployment challenges to Omani graduates. The purpose of this paper is to explore the most common graduate attributes as they apply to graduates' employability in Oman. Design/methodology/approach: The study uses the principles of "hypotheticodeductive logic" and inferential analysis using a combination of focus group and survey approach. Using an online mode of data collection targeting the past three cohorts of graduates from a prominent University in Oman, the study analyses and presents several insights into graduate attributes and employability issues. Findings: The research finds that the domain of educational institutions in Oman is mainly restricted to the basic generic skills in developing the graduate attributes. Students' perspectives on employers' selection criteria reveal that computing skills, the ability to work in teams, English language proficiency, prior training, and the graduate's personality are the five most significant employability skills in Oman. Currently, there is little interaction among higher educational institutions, alumni, and industry in Oman for boosting the employability of graduates. Practical implications: The study is highly relevant from the policy perspective in Oman. All the stakeholders in Oman need to come together to define employability skills prudently by expanding the domain beyond generic skills.Originality/value: The study is important in the context of Oman due to a shortage of studies that look at the graduate attributes from the lens of employability besides addressing concerns about unemployment.