The effect of thermal and shear history on the rheology of waxy crude oils is studied in detail. A protocol sequence is presented, which enables us to systematically extract the main thixotropic features of a model waxy oil by a series of steady state and transient experiments at different temperatures. The importance of the underlying microstructure formed by a loosely aggregated and percolated network of wax crystals is discussed and quantified through differential scanning calorimetry and rheological measurements. The microstructural morphology can be described by relevant concepts used previously in the literature for concentrated suspensions of fractal aggregates and is augmented with evolution equations to capture the transient rearrangement of the microstructure, resulting in a thermokinematic memory of the shearing history and thermal history of the sample. Finally, a complete constitutive framework is derived that is able to quantitatively describe and predict a number of rheological features of the model waxy oil, such as viscoelasticity at small deformations and plasticity at large deformations, with both the yield stress and viscosity exhibiting thermokinematic memory. Direct comparison with rheometric data is used to determine the model constants and evaluate the predictive ability of the constitutive relations. The proposed model provides a new framework that can be used to describe not only waxy crude oils, but also other materials characterized by similar microstructural components, i.e., solid non-Brownian interacting particles of arbitrary shape that form a percolated sample-spanning network and convey thixotropy as well as elasto-viscoplasticity.