Vytshegdosuchus is an extinct genus of paracrocodylomorph archosaur known from the Early Triassic (latest Olenekian stage) Yarenskian Gorizont of the Komi Republic of the European section of Russia.

These specimens were collected from the a fossil assemblage called the Parotosuchus fauna of the Upper Yarenskian Gorizont, in the Zheshart locality along the Vychegda River in Aikino district of the Komi Republic.

Parotosuchus also occurs in Germany within three formations of the Middle Buntsandstein, and is therefore broadly of Olenekian age and considered an index taxon for these strata.

Vytshegdosuchus is from the Gamskian, the upper biochron of the Yarenskian Gorizont and may therefore be latest Olenekian in age and approximately contemporaneous with the poposauroid Ctenosauriscus.

The femur assigned to Vytshegdosuchus is consistent with proterosuchids, Euparkeria and archosaurs since, according to Gower and Sennikov (2000), it has no intertrochanteric fossa and a low fourth trochanter.