The Tuscaloosa Marine Shale (TMS) Formation is a clay- and organic-rich emerging shale play with a considerable amount of hydrocarbon resources. Despite its substantial potential, there have been only a few wells drilled and produced in the formation in recent years. Analyzed TMS samples contain an average of 50 wt% total clay, 27 wt% quartz, and 14 wt% calcite, and the mineralogy varies considerably over the small intervals. The high amount of clay leads to pronounced anisotropy, and the frequent changes in mineralogy result in the heterogeneity of the formation. We studied the compressional- () and shear-wave () velocities to evaluate the degree of anisotropy and heterogeneity, which impact hydraulic fracture growth, borehole instabilities, and subsurface imaging. The ultrasonic measurements of P- and S-wave velocities from five TMS wells are the best fit to the linear relationship with in the least-squares criteria. We observed that TMS S-wave velocities are relatively lower when compared to the established velocity relationships. Most of the velocity data in bedding-normal direction lie outside constant lines of 1.6–1.8, a region typical of most organic-rich shale plays. For all of the studied TMS samples, the S-wave velocity anisotropy exhibits higher values than P-wave velocity anisotropy. In the samples in which the composition is dominated by either calcite or quartz minerals, mineralogy controls the velocities and ratios to a great extent. Additionally, the organic content and maturity account for the velocity behavior in the samples in which the mineralogical composition fails to do so. The results provide further insights into TMS Formation evaluation and contribute to a better understanding of the heterogeneity and anisotropy of the play.