This paper proposes a novel method for horizon detection that combines a multi-scale approach and a convolutional neural network (CNN). The ability to detect the horizon is the first step toward situational awareness of autonomous ships, which have recently attracted interest, and greatly affects the performance of subsequent steps and that of the overall system. Since typical approaches for horizon detection mainly use edge information, two challenging issues need to be overcome: non-stability of edge detection and complex maritime scenes. The proposed method first detects line features by combining edge information from the various scales to reduce the computational time while mitigating the non-stability of edge detection. Subsequently, CNN is used to verify the edge pixels belonging to the horizon to process complex maritime scenes that contain line features similar to the horizon and changes in the sea status. Finally, linear curve fitting along with median filtering are iteratively used to estimate the horizon line accurately. We compared the performance of the proposed method with state-of-the-art methods using the largest database publicly available. The experimental results showed that the accuracy with which the proposed method can identify the horizon is superior to that of state-of-the-art methods. Our method has a median positional error of less than 1.7 pixels from the center of the horizon and a median angular error of approximately 0.1. Further, our results showed that our method is the only one capable of detecting the horizon at high speed with high accuracy, which is attractive for practical applications.