Safe Bayesian optimization (BO) algorithms promise to find optimal control policies without knowing the system dynamics while at the same time guaranteeing safety with high probability. In exchange for those guarantees, popular algorithms require a smoothness assumption: a known upper bound on a norm in a reproducing kernel Hilbert space (RKHS). The RKHS is a potentially infinite-dimensional space, and it is unclear how to—in practice—obtain an upper bound on the norm of an unknown function in its corresponding RKHS. In response, we propose an algorithm that estimates an upper bound on the RKHS norm of an unknown function from data and investigate its theoretical properties. Moreover, akin to Lipschitz-based methods, we treat the RKHS norm as a local rather than a global object and, thus, allow for more optimistic exploration without compromising safety. Integrating the RKHS norm estimation and the local interpretation of the RKHS norm into a safe BO algorithm yields Pacsbo, an algorithm for probably approximately correct safe Bayesian optimization. We demonstrate the effectiveness of Pacsbo and its benefits over popular safe BO algorithms in numerical and hardware experiments.