Efforts to identify Paleolithic dogs or incipient dogs have been based mainly on examination of complete or nearly complete crania. Complete skulls are, however, very rare in the archaeological record. Because canid mandible are far more frequently found in Pleistocene assemblages, the objective of this study is to investigate whether it is possible to differentiate these jaws by metric and osteomorphological methods in two morphotypes: Paleolithic dogs and Pleistocene wolves. This paper is mainly based on the very rich canid assemblage from the Gravettian Předmostí site in the Czech Republic, but also includes a few mandible from several other European Paleolithic sites. This study provides additional evidence of the existence at Předmostí of the two canid morphotypes. The metric data indicate that the mandible of the Paleolithic dogs are shorter than those from Pleistocene wolves in all tested measurements of length, and the carnassial crown length is shorter in Paleolithic dogs compared with the length of this tooth in Pleistocene wolves. Furthermore, in eight of nine indexes, the Paleolithic dogs differ significantly from the Pleistocene wolves. The mandible of Paleolithic dogs differ also in non-metric features from the Pleistocene wolves: they present a high frequency of crowded premolars and backwards-oriented apex of the coronoid. This paper furthermore confirms that Paleolithic dogs occur at two late Upper Paleolithic sites (Eliseevichi, Verholenskaya) where previous studies had indicated their presence. In addition, we document the presence of Paleolithic dogs at another Gravettian site, Kostenki-8.