Marine unmanned vehicle is a novel robot widely used in ocean observation, and its accurate control is of significance to their path planning. We want to find a method to predict the velocity and course of this robot, which can help us realize the accurate control of it. The paper proposed a promising type of hybrid robotic fish (HRF), which can realize two kinds of motion modes on the sea surface. Firstly, the configuration and dynamic model of the HRF were analyzed elaborately. Then, to realize accurate velocity prediction under two kinds of motion modes of HRF, the influence factors are presented in a complex marine environment. Based on the influence factors to its maneuverability, such as wind or wave parameters, a velocity prediction algorithm based on back-propagation neural network (BPNN) was introduced. However, BPNN has the disadvantages of extended learning and training time, easily falling into local optimum. Then we found that genetic algorithm (GA), which is a kind of evolutionary algorithm, is suitable for our problem. Therefore, the accuracy and efficiency of the prediction algorithm were improved by adopting the genetic algorithm to optimize the weight and threshold of BPNN. Taking the experimental data from the pool test, the back-propagation neural network with genetic algorithm (GA-BPNN) forecasting model was established. Besides, the other prediction methods were compared and evaluated under the same assessment criterion to validate the proposed forecasting model. The experimental results demonstrate that the GA-BPNN model has higher accuracy and efficiency compared with other prediction algorithms, which verifies the feasibility of the velocity prediction model for hybrid robotic fish in complex ocean environments.