With the rapid growth of mobile technology, m-government services, which are an extension of e-government, are increasingly becoming an effective alternative. However, similar to other information and communications technology innovations, m-government faces multiple known and unknown challenges at various levels. Although organizational culture has been mentioned in extant literature, this challenge has not been explored in detail, particularly in terms of the dimensions, nature, and overall strength of influence on the innovation itself. This study attempts to fill this void by exploring a particular innovation through an in-depth study in Bangladesh. The framework by Detert et al. (2000) is used as a guide to investigate the various dimensions of organizational culture and characterize the context under study. The paper highlights strong influence of organizational culture and underlines the importance of delving deeper into this influence at every step of such innovation in a developing country, from planning, design, and implementation.