Tourism in Malaysia is one of the important revenue generating activities. One of the groups of tourists that have been increasing in number is the West Asian tourists. The study focused on the tourists loyalty from West Asia toward Malaysia. The objectives of this study are to identify influencing factors on loyalty of West Asian tourists toward Malaysia from the perspectives of West Asian tourists specifically from Kingdom of Saudi Arabia (KSA) and United Arab Emirates (UAE); to examine the relationship between values and satisfaction of West Asian tourists; and to analyze the needs of Malaysian tourists operations in terms of service improvement, with possible policy implications for Malaysian government. This study provides an integrated approach by using the concepts of Tourist Loyalty in relations to Tourist Destination Image, Tour Quality, Tour Values and Tourist Satisfaction in Malaysia from the perspective of marketing theory. Twelve hypotheses were constructed, and examined by utilizing Structural Equation Modeling (SEM) to understand the relationship between the variables. The mixed method of sequential explanatory design consisting of two distinct phases, i.e. quantitative followed by qualitative methods were used in data collection. A total of 541 usable questionnaires out of 562 questionnaires were collected in the first phase, followed by an in-depth interview comprising of nine informants to understand the needs and views of the tourists. Interviews were also conducted with Malaysian tour operators. The results of this research are as follows: first, all direct hypotheses were supported for both countries; however three mediation hypotheses for KSA and two for UAE were not supported. Second, the UAE tourists stated that tourist satisfaction is the most important element in determining tourist loyalty; however, for the KSA tourists, development of family-oriented programs must be given emphasis to ensure tourist loyalty. Finally Malaysian tours operators highlighted the need to focus on the safety of tourists, cleanliness of streets, tourist sites and places most visited by Arabs. The study was completed with conclusion and discussion on the theoretical, methodological and practical implications and suggestions.