A framework for performant Brownian Dynamics (BD) many-body simulations with adaptive timestepping is presented. Contrary to the Euler-Maruyama scheme in common non-adaptive BD, we employ an embedded Heun-Euler integrator for the propagation of the overdamped coupled Langevin equations of motion. This enables the derivation of a local error estimate and the formulation of criteria for the acceptance or rejection of trial steps and for the control of optimal stepsize. Introducing erroneous bias in the random forces is avoided by Rejection Sampling with Memory (RSwM) due to Rackauckas and Nie, which makes use of the Brownian bridge theorem and guarantees the correct generation of a specified random process even when rejecting trial steps. For test cases of Lennard-Jones fluids in bulk and in confinement, it is shown that adaptive BD solves performance and stability issues of conventional BD, already outperforming the latter even in standard situations. We expect this novel computational approach to BD to be especially helpful in long-time simulations of complex systems, e.g. in non-equilibrium, where concurrent slow and fast processes occur.