Human Social, Cultural, and Behavioral Modeling are gaining significant importance in current and future Warfighter training and operational requirements. Peacekeeping and humanitarian missions require the ability to identify civilians' needs and intentions, and to successfully influence or direct their actions. In order to perform successful interviews, rapport building, and negotiations, it is important to recognize non-verbal cues of gesture, facial expression, and body language. However, when interacting with persons of different cultures, we often see behaviors that we think we understand, or use behaviors that we think are understood, but which really have a very different meaning in the other culture. Furthermore, the outward expression of emotion may be suppressed in accordance with varying cultural norms or to avoid the retaliation or censure of others in the community. Ignorance or misunderstanding of these non-verbal cues can make the difference between successful and failed missions. As part of an OSD-Army Research Institute Small Business Innovation Research (SBIR) project, the authors have integrated Virtual Humans with a Cultural Cognitive Architecture to model the culturally-influenced physical behaviors that a Warfighter might experience in face-to-face interactions with persons from non-Western cultures. Using videos of actual discussions and interviews, ethnographic research, and research-based models of culturally-influenced behavior, we developed a cognitive model of an Arab sheikh and the corresponding outward behavior he would likely take during interaction with a Soldier attempting to establish a rapport, obtain information, and influence the sheikh's actions. In this paper, we review methodologies that were tested and used and discuss the methods developed to model the visual cues that were found to be essential to achieve believable and accurate results.