Nameless Things were creatures that are said to have dwelled in the depths of Arda (though they are only known to have lived under the Misty Mountains). They tunnelled deeper than any Dwarf would ever go.
They were described by Gandalf as very ancient, but their actual origin is unknown. They could have been made by Melkor when he created the Misty Mountains. It is also possible the Watcher in the Water is one of these Nameless Things.