In this thesis, we propose a Blockchain-based distributed protocol for enabling deployment of dynamic, on-demand IoT networks. Specifically, the proposed protocol leverages Blockchain technology to: (i) enable distributed and secure authentication, registration, and management of IoT devices; (ii) provide fast discovery of IoT resources and scalable and secure instantiation of on-demand networks; and (iii) manage payment operations and ensure reliable fund transfers among the network entities. The proposed protocol relies on a peer-to-peer network infrastructure to allow communication among the IoT devices in a distributed manner, and uses a self-recovery/self-healing mechanism to ensure robustness against device failure and maliciousness. The protocol also introduces and uses a reputation system to monitor registered devices to keep track of their service delivery quality so that their service delivery reputations could be leveraged for future device selection and mapping. We implemented and evaluated the proposed protocol intensively using simulations to assess its scalability to network sizes and robustness to device failures.