One mission of the International Forum section in "The Counseling Psychologist" is to increase the globalization of counseling psychology (Leong and Ponterotto, 2003). The goals of this study are in line with this mission: (a) to replicate U.S. counseling research on the working alliance to Taiwan by examining clients' perceptions of their counselors' credibility and (b) to extend the working-alliance literature by examining the role that counselors' problem-solving styles play in predicting the initial working alliance. Thirty-one counseling dyads from four counseling centers in Taiwan participated by completing inventories after their first counseling sessions. Results found that (a) clients' perceptions of their counselors' credibility and (b) counselors' perceptions of their problem-solving styles significantly predicted the client-rated, but not the counselor-rated, working alliance. Counseling implications and recommendations for future research are discussed.