Waxy crude oil in pipeline becomes gelled and more compressible because of temperature reduction after prolonged shutdown of the heated oil pipeline. The combined effect of both elasto-viscoplastic thixotropic behavior and compressibility of gelled crude oil plays a critical role on pipeline restart. In the present work, an elasto-viscoplastic thixotropic model was modified to better describe the elasto-viscoplastic thixotropic behavior of gelled waxy crude oil. Then numerical simulations were carried out to investigate the effect of compressibility of gelled crude oil on the restart time and the minimum pressure difference required for successful restart, both of which are of prime importance in engineering practice. The results show that a high compressibility of gelled oil will reduce the minimum pressure difference required for successful restart, and increase the steady-state velocity under given restart pressure. In the initial stage, the propagation velocity of the yield cross-section is equal to the sound speed in gelled crude oil, then gradually decreases during the restart process. With the increase of compressibility of gelled crude oil, the initial propagation velocity of the yield cross-section decreases, while the attenuation of the propagation velocity of the yield cross-section increases. Under this action, the restart time increases.