Fossils of Fruitachampsa have been found from the Fruita Paleontological Area (FPA) in Fruita, Colorado. The deposits in the FPA belong to the Morrison Formation, which is Late Jurassic in age. The first remains of Fruitachampsa were found by paleontologists James Clark and George Callison in 1975, who discovered a diverse assemblage of microvertebrates at the FPA. More complete material of Fruitachampsa was found in 1976, 1977, and 1979. Fruitachampsa has been found alongside another more primitive crocodylomorph, Macelognathus.
The name Fruitachampsa has existed since the late 1980s. Because the name was not published with a formal description, Fruitachampsa was considered a nomen nudum or "naked name." Fruitachampsa callisoni was formally described by James Clark in 2011, with the specific name honoring George Callison.
Most of the body of Fruitachampsa is known from several partial skeletons and skulls. It is a small crocodyliform under 1 metre (3.3 ft) in length. Although small, Fruitachampsa is large in comparison to other shartegosuchids, with a maximum skull length of 9 centimetres (3.5 in). Viewed from above, the skull is square-shaped in the back and narrows toward the snout. The snout is similar in appearance to that of the living caiman genus Paleosuchus, although it is not flattened like in modern crocodylians. As in other early crocodylomorphs, a bone called the palpebral extends backwards over the eye socket like an eyebrow. The teeth at the back of the jaws have flattened tops with ridges running along their length. Unlike other crocodyliforms, Fruitachampsa lacks mandibular or antorbital fenestrae (holes in the lower jaw and in front of the eye sockets). Fruitachampsa differs from other shartegosuchids in that it has procoelous vertebrae with concave anterior surfaces and convex posterior surfaces.
As a terrestrial crocodyliform, Fruitachampsa has long and extremely slender limbs. Bony plates called osteoderms cover the back in two overlapping rows, and are much thinner than those of living crocodylians. Most specimens of Fruitachampsa probably belong to adult individuals because the neural arch is fused to the body of each vertebra, and the sacral ribs are fused to the sacrum. For most living crocodylians, young individuals have many unfused elements in their vertebral column. Other features such as a deeply pitted skull roof and the fusing of the frontal bones in some individuals also suggest that the known material of Fruitachampsa represent mature individuals. Therefore, it is unlikely that Fruitachampsa grew much larger in body size than the specimens indicate.