Ein Knoten, der dem Netz beitreten möchte, muss zuerst einen „Bootstrapping“ genannten Prozess durchlaufen: In dieser Phase erhält der Algorithmus vom Benutzer (oder aus einer gespeicherten Liste) die IP-Adresse eines Knotens, der bereits im Kademlia-Netz bekannt ist. War der Knoten noch nie zuvor im Netz, berechnet er eine zufällige ID, die noch nicht vergeben wurde. Diese verwendet er bis zum Verlassen des Netzes.