Here, we demonstrate the application of fragment-based electronic structure calculations in (a) ab initio molecular dynamics (AIMD) and (b) reduced dimensional potential calculations, for medium- and large-sized protonated water clusters. The specific fragmentation algorithm used here is derived from ONIOM, but includes multiple, overlapping “model” systems. The interaction between the various overlapping model systems is (a) approximated by invoking the principle of inclusion-exclusion at the chosen higher level of theory and (b) within a real calculation performed at the chosen lower level of theory. The fragmentation algorithm itself is written using bit-manipulation arithmetic, which will prove to be advantageous, since the number of fragments in such methods has the propensity to grow exponentially with system size. Benchmark calculations are performed for three different protonated water clusters: H₉O₄⁺, H₁₃O₆⁺ and H(H₂O)₂₁⁺. For potential energy surface benchmarks, we sample the normal coordinates and compare our surface energies with full MP2 and CCSD(T) calculations. The mean absolute error for the fragment-based algorithm is <0.05 kcal/mol, when compared with MP2 calculations, and <0.07 kcal/mol, when compared with CCSD(T) calculations over 693 different geometries for the H₉O₄⁺ system. For the larger H(H₂O)₂₁⁺ water cluster, the mean absolute error is on the order of a 0.1 kcal/mol, when compared with full MP2 calculations for 84 different geometries, at a fraction of the computational cost. Ab initio dynamics calculations were performed for H₉O₄⁺ and H₁₃O₆⁺, and the energy conservation was found to be of the order of 0.01 kcal/mol for short trajectories (on the order of a picosecond). The trajectories were kept short because our algorithm does not currently include dynamical fragmentation, which will be considered in future publications. Nevertheless, the velocity autocorrelation functions and their Fourier transforms computed from the fragment-based AIMD approaches were found to be in excellent agreement with those computed using the respective higher level of theory from the chosen hybrid calculation.