Country Brand Index (CBI) is an index on global perception of a country's image among other countries. In 2012, Indonesia's CBI was ranked 78 from 118 countries, which was lower than the previous years. The Ministry of Foreign Affairs of the Republic of Indonesia have done several efforts to improve the country's image, including social media usage. However, the ministry's social media accounts are not as popular as expected. This indicates the ministry's need of social media strategies for public diplomacy. In order to address this problem, a qualitative research was conducted using semi-structured interview with the ministry's officials and social media experts. Besides, this study employed observations on public diplomacy and social media activities within the ministry. The Strength, Weakness, Opportunity and Threat (SWOT) analysis, McKinsey's 7S Framework, as well as Political, Economic, Social and Technological (PEST) analysis were used to examine the data. The strategy priorities were determined based on Quantitative Strategic Planning Matrix (QSPM). The results indicate five strengths, nine weaknesses, eight opportunities, and six threats for the ministry. The analysis on those factors leads to seventeen social media strategies, which are mapped into six strategic objectives and laid out in a three-year work plan.