Interacting many-body quantum systems and their dynamics, while fundamental to modern science and technology, are formidable to simulate and understand. However, by discovering their symmetries, conservation laws, and integrability, one can unravel their intricacies. Here, using up to 124 qubits of a fully programmable quantum computer, we uncover local conservation laws and integrability in one- and two-dimensional periodically-driven spin lattices in a regime previously inaccessible to such detailed analysis. We focus on the paradigmatic example of disorder-induced ergodicity breaking, where we first benchmark the system crossover into a localized regime through anomalies in the one-particle-density-matrix spectrum and other hallmark signatures. We then demonstrate that this regime stems from hidden local integrals of motion by faithfully reconstructing their quantum operators, thus providing a more detailed portrait of the system's integrable dynamics. Our results demonstrate a versatile strategy for extracting the hidden dynamical structure from noisy experiments on large-scale quantum computers.