Los primeros restos fósiles de "Inostrancevia" fueron encontrados en la localidad de Sokolki del óblast de Arjanguelsk en Rusia como parte de las excavaciones en el Río Dvina Septentrional lideradas por Amalitsky a finales del siglo XIX, en las que se recuperaron dos esqueletos casi completos junto con otros restos esqueléticos.