Single-shot ultra-high-speed imaging is of great significance to capture transient phenomena in physics, biology, and chemistry in real time. Existing techniques, however, have a restricted application scope, a low sequence depth, or a limited pixel count. To overcome these limitations, we developed single-shot compressed optical-streaking ultra-high-speed photography (COSUP) with an imaging speed of 1.5 million frames per second, a sequence depth of 500 frames, and an (x,y) pixel count of 0.5 megapixels per frame. COSUP's single-shot ultra-high-speed imaging ability was demonstrated by recording single laser pulses illuminating through transmissive targets and by tracing a fast-moving object. As a universal imaging platform, COSUP is capable of increasing imaging speeds of a wide range of CCD and complementary metal-oxide-semiconductor cameras by four orders of magnitude. We envision COSUP to be applied in widespread applications in biomedicine and materials science.