Suitable spawning substrates, such as bedrock, boulder/cobble, and gravel, for Paddlefish (Polyodon spathula) that were were mapped in tributaries of Lake Eufaula (Deep Fork River and Brushy Creek) and Hugo Lake (Kiamichi River) via Humminbird Helix 10 sidescan sonar. These datasets show the mosaicked image files and locations of four different substrate types (bedrock, boulder/cobble, gravel, and other) of the river bottom up to 50 km from their reservoir interface. All three rivers contained large amounts of suitable Paddlefish spawning substrate in comparison to other systems with known reproduction.