Valenki are Russian footwear. Traditionally made from wool felt, the word valenok means 'made by felting'. They're not water-resistant (they're just wool after all), and are therefore worn under galoshes to prevent wetness and to preserve the soles. They can be soled with leather or some other durable material, to ensure a longer life, and there are valenki that have rubber soles, for light use in wet conditions.
Valenki are traditionally grey, white, black, brown, tan and myriad other natural hues, but recent commercial valenki are also available in a variety of other colours like red, green, blue, yellow etcetera. Valenki became widespread in use near the middle of the 19th century by industrial mass-manufacture. Before this, due to the labour-intensive process of felting wool, valenki were rather expensive.
The urban popularity of valenki has declined recently, due to the association of the shoes with the rustic lifestyle, but they are still worn by many during the harsh Russian winters.
Personally, I own a pair of grey valenki, and there really is nothing better to wear in the winter than a pair of these felted boots.