In the existing literature, the Japanese market is often characterized with different barriers to entering and doing business. Although these barriers are well documented and researched, earlier investigations focus mainly on barriers related to manufacturing firms, conflicts with distribution channels or give only a general description of the barriers. Most of the previous studies are also cross-industrial and they lack an industry-specific focus. However, almost no research exists on what kinds of challenges foreign small and medium-sized software firms have encountered in the Japanese market. In this research, a multi-case study method was used to investigate the kinds of challenges four small and medium-sized Finnish software firms have encountered in the Japanese market. The findings of this research suggest that it seems to be more reasonable to analyze entry barriers in the software industry at the micro-level rather than using macro-level analyses, as proposed in earlier studies. In this study, a new framework has been developed to analyze the entry barriers. The new framework suggests that barriers for entering and operating in the market are related to the organization, sales process, and the target industry segment. Thus, there seems to be switch from regulatory barriers to requirements set by the business model used.