The solidification of waxy components during the cool down of waxy crude oils in pipelines may provide complex yield stress fluid behavior with time-dependent characteristics, which has a critical impact for predicting flow restart after pipeline shut-in. Here, from a previous set of data at a local scale with the help of Magnetic Resonance Imaging and a new full set of data for various flow and temperature histories, we give a general picture of the rheological behavior of waxy crude oils. The tests include start flow tests at different velocities or creep tests at different stress levels, abrupt changes of velocity level, steady flow, after cooling under static or flowing conditions. We show that when the fluid has been cooled at rest it forms a structure that irreversibly collapses during the startup flow. Under these conditions, the evolution of the apparent viscosity mainly depends on the deformation undergone by the fluid for low or moderate deformation and starts to significantly depend on the shear rate for larger values. Even the (apparent) flow curve of statically cooled waxy crude oils was observed to be dependent on the flow history, more specifically on the maximum shear rate experienced by the material. After being sufficiently sheared, i.e., achieving an equilibrium state, the rheological behavior is that of a simple liquid for shear rates lower than the maximum historical one. A model is proposed to represent those trends experimentally observed. In contrast with most previous works in that field, the model is built without any a priori assumption based on classical behavior of a class of fluids. Finally, it is shown that this model predicts the flow characteristics of these materials under more complex flow histories (sweep tests, sudden shear rate decrease) much better than the so far most often used (Houska) model.