Cultural heritage tourism is the fasted growing segment of the tourism industry, because there is a trend toward an increased specialization among tourists. This is evident in the rise in the volume of tourists who seek adventure, culture, history, archaeology and interaction with local people. Specially, tourists who come to visit Malacca State are interesting in cultural heritage sites have increased recently and are expected to continue. This study attempts to investigate the relationship between cultural heritage destination attributes and tourist satisfaction, and to identify the relationship between cultural heritage destination attributes and tourist satisfaction in terms of selected tourists¡¦ demographic characteristics and travel behavior characteristics. In this study, expectancy-disconfirmation theory was used to provide a conceptual framework. The theory holds that consumers first form expectations of products or service performance prior to purchasing or use. Subsequently, purchasing and use convey to the consumer beliefs about the actual or perceived performance of the product(s) or service(s). Then the consumer will compare the perceived performance to prior expectation. Consumer satisfaction is seen as the outcome of this comparison. The study area for this study was Malacca State, Malaysia. Malacca State is a historical city centre which has been listed as UNESCO World Heritage Site since 7 July 2008. Malacca has adopted as its slogan, ¡§Visiting Malacca Means Visiting Malaysia¡¨, because Malacca have developed over 500 years of trading and cultural exchanged between east and west in the straits of Malacca. Besides that, Malacca also demonstrates the early stages of history originating in the 15th century Malay Sultanate, Portuguese, and Dutch periods beginning in the represents the British era from the end of the 18th century. Furthermore, in year 2009, total of 8.9 million tourists has visited Malacca. It increased about 1.7 million tourists flowing in compared year 2008. The data of this study were collected from the on-site survey method. The sample population for this study was composed of tourists, who visited Malacca State in May, 2010. The survey was conducted at two sites in the cultural heritage sites of Malacca State. Out of 150 questionnaires, 115 were usable. Therefore, the data from 115 respondents were analyzed in this study. A few of appropriate statistical analyses such as frequencies, descriptive, factor analysis, linear regressions analysis, Analysis of Variance (ANOVA), and Analysis of Covariance (ANCOVA) were used according to respective objectives and descriptors. The factor analysis was conducted to create correlated variable composited from the original 23 attributes. Using factor analysis, 23 analysis attributes resulted to three dimensions: General Tour Attraction, Culture and Heritage Attraction, and Differentiate and Amenity Attraction. These three factors then were related with overall satisfaction. The linear regression analysis revealed that was relationship between cultural heritage destination attributes and tourists¡¦ overall satisfaction. ANOVA showed that there was significant difference between derived factor in relation to gender, age, education, country of origin, household income, past experience to cultural heritage sites, length of stay, and information selected, such as internet, newspaper, holiday exhibition, brochure or travel magazine or guidebook, and local or town trail among the demographic and behavior characteristics. The lastly, ANCOVA showed that origin of country, household income per year, and decision time of the control variables controlled the relationship between the overall satisfaction of tourists and derived factors. According to the results of this study, origin of country and household income controlled the relationship between the overall satisfaction of tourists and derived Factor 3 (Differentiate and Amenity Attraction) and time planning showed significant in relationship between the overall satisfaction of tourist of tourists and derived Factor 2 (Cultural and Heritage Attraction). Based on the results several recommendations can be made to improve and increase tourists¡¦ satisfaction of the cultural heritage tourism in Malacca State, such as comprehending what tourists seek at cultural heritage attractions will help tourism marketers better understand their customers. Through this study, planners or marketers can identify which attributes satisfy the tourist who visit cultural heritage destinations will help tourism planners develop appropriate strategies to attract their customers and serve them effectively. Besides that, it allow planners or marketers knowing who the satisfied tourists are may help reduce marketing costs and maintain cultural heritage destinations¡¦ sustainability.