Cyber Security Strategy (CSS) is a high-level organization plan of protecting its assets through Information and Communication Technologies (ICTs) to accomplish business objectives efficiently. A CSS provides a collection of frameworks, procedures, and corresponding objectives that aim to achieve certain quality in securing the organization's infrastructure. Since today's organizations are highly dependent on ICTs, implementing, and maintaining CSS is crucial. From the literature review, it is evident that such factors are abstractly stated. Also, no holistic study exists that lists or evaluates the critical factors in the public sector. The objective of our work is to explore and identify the critical factors influencing the implementation of CSS in public sector organizations in Oman. This research is the first study to explore the critical factors needed to implement CSS in the public sector in Oman, provide a distinct and well-structured list of factors that will help the public sector's organizations of Oman to implement CSS successfully. It will also serve as an important source of reference for future researchers in general for the private and public sectors. The study also confirms how the nature of public organizations differs for the private ones when it comes to economics factor. It shows how those factors are a necessity for any organization as well. This research also generates a list of factors that can be a basis in evaluating a framework for assessing the effectiveness of a given CSS. To achieve the sought aims, we adopted a qualitative research methodology by conducting semistructured interviews with 10 participants having extensive experience in security settings to confirm the critical factors.