This work presents, for the first time, a novel fractal phononic crystal (PC) design in epitaxial cubic silicon carbide (3C-SiC) and experimentally demonstrates acoustic band gaps (ABGs) in the ultra high frequency (UHF) range. The unit cell consists of an air scatterer in a SiC host matrix. Unlike most conventional PC designs, either having circular holes or cylindrical pillars as the scattering sites, the shape of the fractal-like scatterer is formed by a center square hole with four repeating smaller squares at its corners. The fractal nature of this design enables opening phononic band gaps (PBGs) at higher operating frequencies than conventional designs, therefore attaining UHF operations with larger features. The micromachined SiC PBG structure exhibits two frequency stop bands in the 1 GHz range, centered at 990 MHz and 1.17 GHz with 10 % and 15.4 % gap-to-midgap ratio bandwidth, respectively.