Mobile handheld devices such as smart cellular phones are easily lost or stolen because of their small sizes and high mobility. Personal data such as addresses and messages stored in the devices may be revealed when the devices are lost. Handheld devices must include rigorous and convenient handheld data protection in case the devices are lost or stolen. This research proposes a novel approach for handheld data protection by using handheld usage data mining, which consists of five steps: (i) usage data gathering, (ii) usage data preparation, (iii) usage pattern discovery, (iv) usage pattern analysis and visualization, and (v) usage pattern applications. Handheld usage data is collected before applying this method. Usage patterns are discovered and saved by using finite automaton, which is then used to check device usage. When an unusual usage pattern such as an unlawful user trying to access the handheld data is detected, the device will automatically lock itself down until an action, such as entering a password, is taken. Experimental results show this method is effective and convenient for handheld data protection.