While change seems to have become a feature of contemporary organizations, the success rate of change initiatives is admittedly very poor, not only when initiating the change, but even after the successful implementation of a well-planned change, as employees are likely to return to their old habits; thus most change efforts do not persist. Organizations however need to ensure that their change initiatives, which in most cases come at a heavy cost in terms of investment, last long enough to attain their goals. Given the lack of change management research in the Middle Eastern context, particularly with respect to the institutionalization of change, this study explores how best to institutionalize change interventions in the Middle East. The research employs a mixed-methods approach, combining semi-structured interviews with 17 senior managers and a questionnaire survey of 312 employees, in order to gather data from the case study of the Abu Dhabi Police. The quantitative data is assessed using descriptive and inferential statistical analysis, while the independent samples t-test is used to explore variations between groups. The findings reveal the significant role of communication in creating shared meanings, perceptions and interpretations; the language-based approach is thus recommended as an additional conversational instrument to enlighten managers and enrich their interventions. This study identifies four categories of factors that are critical to institutionalization; the characteristics of these critical factors and associated issues are also highlighted as a contribution to the design and implementation of institutionalization strategies. The study concludes by developing a framework incorporating three basic conceptual elements that should be considered as a whole during any attempt to institutionalize change; it comprehensively integrates the institutionalization strategies and the critical factors, in order to convey a change message that shapes the enactment of institutionalization processes.