The heritage city of Melaka is one of the top most visited destinations in Malaysia by both domestic and international tourists. It has a mixture of heritage attractions that correspond to its status as one of the World Heritage Sites. Thus, the level of tourists' expectations and satisfaction needs to be analysed so as to identify the strengths and weaknesses of the Heritage City of Melaka. This research is based on the expectation and satisfaction of both first time and return tourists of the Heritage City of Melaka. Questionnaires were used as a medium to acquire the relevant information about these levels from the tourists. The expectation and satisfaction of the tourists were measured based on the dimensional elements of heritage attractions. The results of this experiment show that there is a significant difference of expectation between a first timer and a return tourist towards art (music/ dance) at the significant level of p < 0.01 and six other elements at the significant level of p < 0.05, which include the historical buildings, traditional views, traditional handicraft, monuments, museums and traditional villages. For the satisfaction level, however, only traditional views in the study area have a significant difference between a first timer and a return tourist at the significance level p < 0.05. In conclusion, first timer and return tourists have different expectations but a similar level of satisfaction on the elements of heritage attractions in the Heritage City of Melaka.