Newcomers to a country often face difficulties in adapting to the new healthcare system. Understanding their perceived barriers in utilizing healthcare services in the host country is crucial for designing health IT to meet their health needs. In this paper, we present an interview study of 30 international students attending a U.S. university. We identified barriers that hindered them from accessing health services in the host country -- difficulties in understanding health services information, high healthcare costs, unfamiliar and cumbersome health practices, negative beliefs toward western medicine, and communication and language barrier. We also uncovered their alternative solutions by actively seeking health services information, adopting preventive measures, and self-diagnosing and self-treating with medicine brought from their home countries. Finally, we derived implications for designing health IT and services to better support international students' healthcare.