Bedforms on Earth and Mars are often preserved in the rock record in the form of sedimentary rock with distinct cross-bedding. On rare occasions, the full-surface geometry of a bedform can be preserved through burial and lithification. These features, known as paleobedforms, are found in a variety of geographic locations on Mars. Evidence in the morphology of paleobedforms, such as the retention of impact craters and steep erosional scarps, suggests that these features are well-lithified and capable of withstanding prolonged weathering and erosion. Here, we present results from thermophysical and compositional analyses on a subset of the best preserved paleobedform candidate fields on Mars. Thermophysical modeling elucidates the changes these bedforms underwent from their unconsolidated, particulate nature to their currently observed properties. Certain paleobedforms have elevated thermal inertias (e.g., ∼300–500 J·m⁻²·s^−1/2·K⁻¹) when compared with modern bedforms (∼250 J·m⁻²·s^−1/2·K⁻¹), and modeling indicates that they have cement volumes of 0.8%–1.5% even as high as 30%. However, most paleobedform candidates have unexpectedly low thermal inertia when compared with modern dunes. Additionally, compositional analyses reveal a range of spectral characteristics within paleobedforms (e.g., primary and secondary alteration products). These features add to the already existing class of Martian surfaces in which thermal inertia does not seem to correspond to erodibility, cohesion, or mechanical strength. Studying paleobedforms with both raised and nonraised thermal inertia has provided new insights into lithification on Mars and constrained the environmental conditions leading to the formation of these enigmatic features.