Efficiency evaluation has become an important improvement tool for hotels to sustain in todays highly competitive environment. This study used DEA approach to evaluate the relative efficiency of a Malaysian hotel chain during the period of 2004 to 2008 in terms of Total Factor Productivity (TFP) change. TFP change is measured using DEA-Malmquist productivity index. DEA is a pragmatic tool which combines multiple inputs and outputs objectively onto an overall measure of organizational efficiency. The Malmquist TFP index measures are decomposed into technical efficiency change and technological change. The decomposition of technical efficiency change into two sub-components, pure technical efficiency change, and scale efficiency change is also discussed in this paper. The actual operating data of five inputs and five outputs were collected from 10 hotels under the chain. Empirical results revealed that the TFP of the hotel chain slightly increased by 0.7% over the time period. Six of the hotels in the chain experienced positive TFP change while the others experienced TFP decline. The quadrant of efficiency was proposed to give a two-dimensional view of the hotel efficiency. Meanwhile, technological change was found to be more important factor of TFP growth as compared to technical efficiency change. Therefore, hotels which faced negative growths of technological change are recommended to improve their efficiency through investment in new technology or by upgrading the necessary skills. Additionally, the paper has also identified the best performing hotel within the chain which can be benchmarked by others who are seeking for performance improvement.