Levy flight random walk is one of the important operators of cuckoo search (CS) algorithm, and it employs the fixed step size factor to generate new candidate solutions. In this work, the memory mechanism is introduced into CS algorithm to dynamically select the appropriate step size, which differs from many CS variants by incorporating some existing algorithms into CS framework. To investigate the effectiveness of the presented version, two well-known test suites are employed. Experimental results demonstrate that CS with memory (CSM) exhibits better optimization performance compared with other CS variants. Then, a vibration fault diagnosis model of hydroelectric generating unit (HGU) based on CSM combined with BP neural network is established. Diagnostic results show that the combined model has higher classification accuracy in tackling two diagnostic examples, and also prove the superiority of the proposed algorithm in solving practical problems.