The construction industry is characterized with a high rate of work-related accidents. Some of the accidents result in severe injuries and sometimes death. One of the reasons for such happenings is due to the noncompliance of the construction companies to the Occupational Health and Safety (OHS) regulatory framework. This paper briefly describes the preliminary results of the first part of an ongoing study. The study is composed of three parts studying the OHS practices in small and medium construction companies in Oman. The three parts are (1) identifying the level of compliance of the small and medium construction companies to the OHS regulatory framework, (2) comprehensively identifying the causation of the non-compliance and the risk generated, and (3) proposing a framework for “Paving Zero Accident Vision” in Oman. Oman’s OHS regulatory framework was used to construct an evaluation survey. Sixty small and medium construction companies from two different governorates, Muscat and South Al Batinah, were involved in the study. Three evaluation results related to the construction site fencing, the nature of the project site, and the level of compliance to providing personal protective equipment were reported. The results showed that the 75.5% on an average, the construction companies fenced their construction site; for 59% on average the project site is a construction and an accommodation site at the same time, and the level of compliance to providing Personal Protective Equipment (PPE) is varying in both locations. However, both locations showed similar results in providing ear protection, eye protection, and safety shoes.