We demonstrate a novel artificial optical material, the "photonic hyper-crystal", which combines the most interesting features of hyperbolic metamaterials and photonic crystals. Similar to hyperbolic metamaterials, photonic hyper-crystals exhibit broadband divergence in their photonic density of states due to the lack of usual diffraction limit on the photon wave vector. On the other hand, similar to photonic crystals, hyperbolic dispersion law of extraordinary photons is modulated by forbidden gaps near the boundaries of photonic Brillouin zones. Three dimensional self-assembly of photonic hyper-crystals has been achieved by application of external magnetic field to a cobalt nanoparticle-based ferrofluid. Unique spectral properties of photonic hyper-crystals lead to extreme sensitivity of the material to monolayer coatings of cobalt nanoparticles, which should find numerous applications in biological and chemical sensing.