A Low Autocorrelation Binary Sequence (LABS) problem is a hard combinatorial problem and its solutions are important in many practical applications. Till now, the largest best-known skew-symmetric sequence with merit factor greater than 9 had a length of 189. In this paper, a new heuristic algorithm is presented for the LABS problem. The proposed algorithm stores promising solutions and this mechanism enables the algorithm to perform local searches on these solutions in a systematic way. Our algorithm was tested on skew-symmetric sequences and the obtained results are compared with results of the state-of-the-art algorithms. The proposed algorithm was able to find some new best-known skew-symmetric solutions with merit factor greater than 9 in sequence lengths over 200. The obtained results improve the suggestion from 1985 (Beenker et al.) and 1987 (Bernasconi) greatly, where the merit factor is approximately equal to 6 for long skew-symmetric sequences with length up to 199. Now, the largest best-known skew-symmetric sequence with merit factor greater than 9 has the length 225. Additionally, now all merit factors are greater than 8.5 on the interval from 159 up to 225 for odd lengths.