Through the design and manipulation of discrete, nanoscale systems capable of encoding massive amounts of information, the basic components of computation are open to reinvention. These components will enable tagging, memory storage, and sensing in unusual environments – elementary functions crucial for soft robotics and “wet computing”. Here we show how reconfigurable clusters made of N colloidal particles bound flexibly to a central colloidal sphere have the capacity to store an amount of information that increases as O(N ln(N)). Using Brownian dynamics simulations, we predict dynamical regimes that allow for information to be written, saved, and erased. We experimentally assemble an N = 4 reconfigurable cluster from chemically synthesized colloidal building blocks, and monitor its equilibrium dynamics. We observe state switching in agreement with simulations. This cluster can store one bit of information, and represents the simplest digital colloid.