Cloud computing is an emerging industry in Taiwan. Since this industry relies heavily on information communication technology (ICT) infrastructure, a telecom operator can play an important role in the establishment of cloud computing industry. In this paper, we adopt an organizational legitimacy approach to understand how a telecom company in Taiwan develop legitimacy strategy for cloud computing services. Our preliminary data analysis indicates that an organization can adopt multiple strategies to achieve legitimacy at organizational, industry and institutional levels. This study is expected to make contributions on enhancing practical understanding on organization’s strategy in forming the nascent market.