Holography is a powerful tool for three-dimensional imaging. However, in explosive, supersonic, hypersonic, cavitating, or ionizing environments, shock-waves and density gradients impart phase distortions that obscure objects in the field-of-view. Capturing time-resolved information in these environments also requires ultra-high-speed acquisition. To reduce phase distortions and increase imaging rates, we introduce an ultra-high-speed phase conjugate digital in-line holography (PCDIH) technique. In this concept, a coherent beam passes through the shock-wave distortion, reflects off a phase conjugate mirror, and propagates back through the shock-wave, thereby minimizing imaging distortions from phase delays. By implementing the method using a pulse-burst laser setup at up to 5 million-frames-per-second, time-resolved holograms of ultra-fast events are now possible. This technique is applied for holographic imaging through laser-spark plasma-generated shock-waves and to enable three-dimensional tracking of explosively generated hypersonic fragments. Simulations further advance our understanding of physical processes and experiments demonstrate ultra-high-speed PCDIH techniques for capturing dynamics.