Phononic crystals, artificial materials with periodically arranged scattering centers, were introduced more than two decades ago as the elastic waves analogue of photonic crystals. These materials, either in two or three dimensions, can exhibit large frequency regions of prohibited propagation of elastic waves, the so-called phononic band gaps (PBGs). On the other hand, typical elastic wave propagation in random structures is associated with diffusion, or in extreme situation with localization, and random structures do not exhibit band gaps. Here, we introduce a new class of structurally disordered phononic structures, hyperuniform disordered phononic structures (HDPS) that exhibit large elastic band gaps. These structures are created from initially arbitrary point patterns by imposing hyperuniform correlations among the points and finally decorating them with a specific scatterers, so that the structure factor becomes isotropic and vanishes for all k-vectors within a specific radius. The disorder can smoothly be tuned to produce structures ranging from totally random to fully periodic by adjusting a single parameter. Such amorphous structures exhibit large band gaps, comparable to the ones found in the periodic counterparts, ballistic and diffusive propagation depending on the modes frequency and a large number of localized modes near the band edges. We discuss the formation of high-Q cavity modes and waveguides with 100% transmission in these disordered structures in the GHz regime. Such phononic-circuit architectures are expected to have a direct impact on integrated micro-electro-mechanical filters/modulators for wireless communications and acoustic-optical sensing devices.