Окаменелости валдозавра были впервые обнаружены в 1848 году, но считались олицетворением игуанодона. Сто лет спустя и палеонтолог Питер М. Гальтон определил что это новый вид.
После этого к валдозавру стали добавляться дополнительные посткраниальные останки, причем окаменелости из таких отдаленных мест, как Румыния и Нигер, были идентифицированы как разновидности валдозавра. Однако многие из них в настоящее время подвергнуты сомнению, а некоторые из них были использованы для создания новых родов динозавров, таких как Elrahzosaurus из Нигера. На данный момент единственным видом валдозавра является вид V. Canaliculatus, определенный по двум отдельным бедрам.