Page replacement algorithms in most operating systems are optimized for disk based systems. However, in recent years, embedded systems are usually equipped with NAND flash memory because it has many attractive features such as small size, fast access speed, shock resistance, and lightweight. Therefore, a new replacement algorithm is needed for NAND flash memory based embedded systems. In this paper, we propose a new replacement algorithm for embedded systems with NAND flash memory. The proposed algorithm focuses on reducing the replacement cost and I/O execution time in order to improve the performance of embedded systems. Trace-driven simulations show that the proposed algorithm performs better than existing algorithms in terms of the replacement cost and I/O execution time.