Photonic crystals (PCs) consisting of a periodic arrangement of holes in dielectric media have found success in light manipulation and sensing. Among them, three-dimensional (3D) PCs are in high demand due to their unique properties originating from multiple photonic band gaps (PBGs) and even full ones. Here, 3D PCs based on porous anodic aluminum oxide (AAO) were fabricated for the first time. Our approach involves prepatterning of the aluminum surface by a focused ion beam to form a hexagonal array of pore nuclei. Subsequent anodization in 1 M H3PO3 using a sine wave profile of voltage provides AAO with a defect-free in-plane porous structure and out-of-plane porosity modulation. The ability to tune the position, width, and depth of the PBGs is demonstrated. The combination of the flexibility of the proposed approach with the unique properties of AAO extends the range of practical applications of 3D PCs far beyond the current achievements.