International students in U.S. academic settings are facing barriers in the path of their academic accomplishments. In higher educational institutions, students work very closely with their academic advisors to solve a definite problem. Dependence on the academic advisor is much more when the advisee is international. Keeping these points in mind, one of the factors that might impact academic environment for an international student is the bonding that they share with their advisor. This research study determines the factors that encourage or discourage the relationship between the advisor and international advisee. More specifically, what factors, cultural or cognitive are more salient in defining the advising relationship, and how are coping behaviors being employed and by whom when differences between the working pair exists? Full-time international graduate students having at least one year of graduate school experience in U.S. academic settings and faculty advisors who had experience in advising international graduate students participated in this study. A total of 20 international students participated. All the participants completed the Kirton Adaption-Innovation Inventory (KAI) as a measure of problem-solving style. Of the 20 that completed the inventory, 14 participants from 10 different countries agreed to participate in a semi-structure interview. Additionally, five faculty advisors completed the KAI inventory and three faculty advisors participated in an interview. Findings of the study are: 1) a link exists between participants' problem-solving styles and their expectations for the advising relationship; 2) cultural difference outside academia had no impact on academic progress of international students; 3) acculturation into American academic culture seemed essential for academic success of international students in U.S academic settings; 4) international students wanted their home country culture to be acknowledged in a multicultural settings; 5) success of advising relationship seemed to be dependent upon how much the advisor and the advisee exhibited coping behavior; 6) acknowledging the differences and accepting a person in a holistic manner as a separate identity worked best in a multicultural settings; and 7) developing a human connect between the advisor and advisee seemed to be vital for a successful and academically productive advising relationship.