Mobile robots with wireless capabilities can enable network connectivity over large areas by retransmitting wireless signals from a ground station. Our goal is, for such robotic networks, to enhance current teleoperated robots’ ability to perform reconnaissance or assist human first responders on victims’ search and rescue operations. On these missions, uninterrupted communications between teleoperated robots and their human operators are essential. In order to maximize the teleoperated robots’ working area, the robotic network has to deploy itself, in an unknown and potentially hazardous environment, spreading as much as possiblewithout losing network connectivity. In this paper, we consider an urban search and rescue setting; and present a distributed algorithm that allows simple mobile robots to self-deploy and create robotic networks, without the need of advanced self-localization capabilities nor prior knowledge of the environment.