Red sandstone samples treated at high temperatures feature complex creep properties. Uniaxial compression tests and the incremental creep tests at different stress gradients were conducted on 10 red sandstone samples of the same specifications divided into five groups on an RLW-2000 triaxial servo rheometer in the laboratory. Relationships of the instantaneous strain and creep strain of red sandstone samples treated at high temperatures with the stress level were explored, and the creep properties and strength of the samples at different temperature gradients were investigated. In addition, the creep failure patterns and failure mechanism of the red sandstone samples were determined, and a creep constitutive model was established for the samples considering the effects of temperature. The conformity between test data and theoretical curves was discussed. Results show that as the stress increases, the instantaneous strain tends to decrease rapidly, slowly, then increase slowly; the creep strain tends to decrease, steadily increase, then increase substantially. At the same stress, as the stress gradient is doubled, the instantaneous strain decreases by 47.45%, and the creep strain decreases by 48.30%. For samples treated at 300~900 °C, the number of stress levels experienced gradually decreases; as the temperature increases, the creep failure strength of samples first increases, then decreases in an arcuate form, and the creep strain tends to decrease, increase, then increase rapidly. In the temperature range, the creep strain at the two stress gradients has a growing difference, with the maximum difference reaching 0.0134%; there is an inflection point at 300 °C in the creep failure strength of samples. At the same stress, the more the stress levels experienced, the lower the creep failure strength, and the temperature, creep failure strength, and creep strain can be characterized by a quadratic polynomial. At 300 °C, mineral particles in samples are sintered and cemented into chains, and there is a significant primary control plane, so the samples show oblique shear failure of a single primary control plane. At 600~900 °C, particles and blocks in samples begin to be sintered and flow, and the cemented chains are broken. Under the condition, the samples mainly show failure dominated by mixed and crossed primary and secondary control planes and crushing failure due to transverse compression. The established Burgers−Kelvin-Temperature (BKT) creep constitutive model is sensitive to changes in temperature; the theoretical curves are consistent with the test data.