Achieving an estimation of viscosity in crude oil binary mixtures is often difficult because the relationship of viscosity, to the fraction of each crude oil, and many other parameters and constants is comply. This relationship can be expressed by mathematical models with different variables. Besides the known models for predicting the viscosity of crude oil mixtures, the petroleum industry demands other models which give accurate predictions. In this work, two new empirical models have been developed for the calculation of the viscosity of binary crude oil blends. Two techniques—least square (LS) and genetic algorithm (GA)—were used to determine the parameters of the proposed models. Dynamic viscosity of 12 sets of crude oil blends at 298.15 K and 25 different shear rates were measured, resulting in 300 sets of binary data. Moreover, 700 sets of kinematic viscosity binary data were collected from literature sources and used along with 200 of the 300 sets of experimental binary data with a wide range of American Petroleum Institute (API) gravity (9.89–41.2) and viscosity (1.054–165,860 cSt) to examine existing available models as well as the newly developed models in this study. The remaining 100 experimental data points which were not used in the regression process were used for validating the models. The results in terms of the absolute average relative deviation (AARD%) were 33.546 and 14.195 for the LS method and 13.113 and 13.672 for the GA method for proposed models one and two, respectively. The results of statistical parameters based on the GA and LS methods showed that the GA is a superior method for new model parameter estimation as compared with the traditional LS technique. The GA-based models developed in this study provided the highest accuracy for viscosity calculation of the crude oil blends over all existing models in the literature.