Learning a diverse set of skills by interacting with an environment without any external supervision is an important challenge.In particular, obtaining a goal-conditioned agent that can reach any given state is useful in many applications. We propose a novel method for training such a goal-conditioned agent without any external rewards or domain knowledge about the environment.The first component of our method is a \emph{reachability network} that learns to measure the similarity between two states from random interactions only.Then this reachability network is used to build the second component, a memory of past observations that are diverse and well-balanced.Finally, we train a goal-conditioned policy network, the third component, with goals sampled from the memory and reward it by the scores computed by the reachability network.All three components are kept updated throughout training as the agent explores and learns new skills.We demonstrate that our method allows training an agent for continuous control navigation, as well as robotic manipulation.