We determine the acoustic velocities for samples cored from the Jauf and Unayzah sandstone formations of Saudi Arabia. We use microstructural analysis including thin sections and point counting to quantify cementation. Velocities in these formations are strongly controlled by the combination of porosity and cementation. Consequently, rocks of similar porosity but with different cementation materials display different velocities. The objective of this study is to understand the effect of cementation on the acoustic velocity. Cements in these two formations have variable compositions and properties. Pure quartz overgrowth plays a major role in increasing velocities while clay and clay coatings play a minor role. We found that clay coatings inhibit the quartz overgrowth cement leading to a decrease in velocities. Understanding the influence of various cementation types on velocity, and thus elastic properties in sandstone cores, enables an understanding of the variation of sonic velocities and moduli across these formations. The uniqueness of this study is that we emphasize the quantification of the role of cement and not just mineral volume.