Binary sequences with low aperiodic autocorrelation levels, defined in terms of the peak sidelobe level and/or merit factor, have many important engineering applications, such as radars, sonars, spread spectrum communications, system identification and cryptography. Searching for low autocorrelation binary sequences (LABS) is a notorious combinatorial problem, and has been chosen to form a benchmark test for constraint solvers. Due to its prohibitively high complexity, an exhaustive search solution is impractical, except for relatively short lengths. Many suboptimal algorithms have been introduced to extend the LABS search for lengths of up to a few hundreds. In this paper, we address the challenge of discovering even longer LABS by proposing an evolutionary algorithm with a new combination of several features, borrowed from genetic algorithms, evolutionary strategies and memetic algorithms. The proposed algorithm can efficiently discover long LABS of lengths up to several thousands. Recordbreaking minimum peak sidelobe results of many lengths up to 4096 have been tabulated for benchmarking purpose. In addition, our algorithm design can be easily adapted to tackle various extensions of the LABS problem, say, with a generic sidelobe criterion and/or for possibly nonbinary sequences.