The genus is known primarily from the Late Cretaceous, Turonian to the Campanian stage, Hell Creek Formation deposits. Paleopsephurus is one of only two known paddlefish genera to have been found in the North American fossil record, with the genus and species Crossopholis magnicaudatus only being described and found in the Early Eocene Green River Formation. A third extinct genus Protopsephurus with the single species Protopsephurus liui was described from China in 1994. Only two modern paddle fish species are known, Polyodon spathula in the Mississippi River system of North America, and the possibly extinct Psephurus gladius in the Yangtze River of China.
The genus was described from three partial specimens currently residing in the collections of the University of Michigan Museum of Paleontology in Ann Arbor, Michigan, USA. Specimen number 22206 U.M. is a complete and well preserved skull with some denticles,pectoral girdle and pectoral fins. The second and third specimens were found in a block of matrix from the same location as 2226 U.M.. Specimen 22207 U.M. is a portion of the caudal region of a paddlefish, while 22208 U.M. is a partial shoulder with associated pectoral fin. While the specimens were found close to each other, it is impossible to determine if they represent a single individual, and as such were described as three separate fish specimens. The specimens were collected from a sandstone outcrop of the Hell Creek Formation 24 miles (39 km) southeast of Fort Peck Montana by a University of Michigan Museum of Paleontology expedition expidition in 1938. the fossils were in close association with the holotype specimen of the extinct sturgeon Protoscaphirhynchus squamosus.
The Paleopsephurus specimens were first studied by American paleontologist and ichthyologist Archie Justus MacAlpin. He published his detailed 1947 type description in the journal Contributions from the Museum of Paleontology, University of Michigan.