A large data set is generally needed when modeling hydrological processes. However, for developing countries such as China, data sets are often unavailable in remote areas. An attempt to apply a novel genetic programming (GP) technique was made to model the relationship between streamflow of the West Malian River and the impact of climate change in the northeastern part of China. Available annual streamflow and climatic data were used for training and testing of the GP model. Data from the years between 1982 and 2002 were used for automatic selection of the model relationship. Prediction of the model was undertaken for the period 2003–2006 and the results were compared with measured data. Predicted annual streamflow of the West Malian River agreed with measured data to an acceptable degree of accuracy even with a small amount of data set. For comparison, a multilayer perceptron method with back propagation algorithm, a gray theory model, and a multiple linear regression model were selected to conduct the prediction with the same data set. Results showed that the performance of GP method was generally better than other statistical methods such as multilayer perceptron, gray theory model, and multiple linear regression model. Further, the results also showed that the GP method is a useful tool for water resource management, especially in developing countries, to evaluate the potential impacts of climate change on the streamflow when large data sets are unavailable.