The Sea Surface Temperature (SST) is one of the key factors affecting ocean climate change. Hence, Sea Surface Temperature Prediction (SSTP) is of great significance to the study of navigation and meteorology. However, SST data is well-known to suffer from high levels of redundant information, which makes it very difficult to realize accurate predictions, for instance when using time-series regression. This paper constructs a simple yet effective SSTP model, dubbed DSL (given its origination from methods known as DTW, SVM and LSPSO). DSL is based on time-series similarity measure, multiple pattern learning and parameter optimization. It consists of three parts: (1) using Dynamic Time Warping (DTW) to mine the similarities in historical SST series; (2) training a Support Vector Machine (SVM) using the top-k similar patterns, deriving a robust SSTP model that offers a 5-day prediction window based on multiple SST input sequences; and (3) developing an improved Particle Swarm Optimization (PSO) method, dubbed LSPSO, which uses a local search strategy to achieve the combined requirement of prediction accuracy and efficiency. Our method strives for optimal model parameters (pattern length and interval step) and is suited for long-term series, leading to significant improvements in SST trend predictions. Our experimental validation shows a 16.7% reduction in prediction error, at a 76% gain in operating efficiency. We also achieve a significant improvement in prediction accuracy of non-stationary SST time series, compared to DTW, SVM, DS (i.e., DTW + SVM), and a recent deep learning method dubbed Long-Short Term Memory (LSTM).