Machine Learning-assisted metaheuristics is a new and promising research topic, combining the advantages of both method families. Metaheuristics are widely used general problem solvers that can be fine-tuned by prior knowledge about the search space; however, this adaptation can be a very time-consuming and complex task. This paper proposes a hybrid variation of the Hill Climbing method using a Machine Learning model to learn this domain-specific knowledge in advance to help determine the optimal step size of each iteration. A Deep Feedforward Neural Network was trained on the steps of thousands of Hill Climbing runs. This model was used in a novel alternating method (using traditional and Machine Learning-based steps) to predict the optimal step size for each iteration. This hybrid algorithm was compared to the already-known variants. The results show that the novel hybrid method is able to find slightly better results than the original Hill Climbing method, requiring significantly fewer fitness calculations.