Establishing a business in China has always been perceived as a challenge to foreign firms. In addition to the resource- and industry-based conditions, firms need to take into account the wide influence of Chinese organizations and cultural differences from home countries, as well as guanxi, a central Chinese business concept that refers to the benefits gained from social connections. While the Chinese legal and political system in the field of business has improved in recent years, this study adopts an institution-based framework to illustrate the constraints and strategies in setting up a foreign investment enterprise (FIE) in China from a Norwegian enterprise’s perspective. More specifically, since China suffers from substantial regional inequalities and levels of law enforcement thus vary widely, this study explores the regional levels of law enforcement in different provinces in China. In addition, this study analyzes the entry mode strategies based on formal and informal institutional considerations. The statistical data are from surveys of Norwegian small- and medium-sized enterprises (NSMEs) and secondary data collection. A case study is undertaken to discuss what actions NSMEs can take in setting up an FIE in China. The research reveals that NSMEs that are culturally remote from China need to better verify the legal requirements, adapt to the culture, and practice guanxi with relevant organizations to determine their best-fit entry mode strategy and location decision during the process of setting up an FIE in China.