Cultural heuristics determine acceptable verbal and non-verbal behavior in interpersonal encounters and are often the main reason for problems in intercultural communication. In this article, we present an approach to intercultural training of non-verbal behaviors that makes use of enculturated virtual agents, i.e. interactive systems that take cultural heuristics for interpreting and generating behavior into account. Because current trends in intercultural training highlight the importance of a coaching approach, i.e. the ability to offer training units anytime and anywhere, the system was developed as a mobile solution taking the sensoric capabilities of smart phones into account for the user interaction in form of gesture recognition. After an introduction of the theoretical background on culture and enculturated systems, the system features are discussed in detail followed by an account of the application itself, emphasizing the importance of situated role-plays. Two evaluation studies are presented next that analyze the usability of the approach as well as the more important question of whether training with the system gives better results than traditional methods.