In this work, high density and small size metal nanodots (MND) with different work-functions were fabricated as a floating gate of nonvolatile memory (NVM) devices by self-assembled nanodot deposition (SAND). The energy band engineering of NVM was demonstrated through controlling MND work-function. For single MND layer floating gate NVM, the retention time was improved by choosing high work-function MND. Furthermore, we proposed a new type NVM with a double stacked MND floating gate. Here, the high work-function MND are placed on the top layer and the low work-function MND are placed on the bottom layer. A large memory window and long retention time were obtained. However, the thermal electron excitation is dominant for the electron discharge process during retention. How to reduce the defects in MND layer is important for further improving of memory characteristics.