The Paddlefish (Polyodon spathula) has been extirpated from portions of its native range due to anthropogenic habitat degradation and fragmentation, most notably the impoundment of rivers. To mitigate some of these losses in Oklahoma, Paddlefish have been stocked into reservoirs throughout the state, with variable success in establishing self-sustaining populations. Two factors thought to contribute to success of Paddlefish stocking are spawning substrate and prey availability, which were quantified in six reservoirs and nine reservoir tributaries. Side-scan sonar and supervised classification of aerial imagery were used to classify 4517-ha of river substrate upstream of the river-reservoir interface in reservoir tributaries. Zooplankton community structure, water clarity, and nutrient availability were also assessed in the same reservoirs and tributaries. One tributary had suitable spawning substrate (>40%), and the rest had minimal (<1.5%), which suggested that availability of suitable spawning substrate was not directly correlated with Paddlefish stocking success. Reservoirs with self-sustaining Paddlefish populations had higher abundance of large zooplankton (copepods and cladocerans) than reservoirs without a reproducing population. Notably, tributaries associated with Lake Texoma, the one known example of failed restoration, were much more turbid than other rivers. We conclude that abiotic factors such as water clarity may contribute more to variable recruitment than spawning substrate or zooplankton abundance by mediating foraging success of Paddlefish post-larvae.