First-in first-out (FIFO) memories are widely used in SoC for data buffering and flow control. In this paper, a robust ultra-low power asynchronous FIFO memory is proposed. With self-adaptive power control and complementary power gating techniques, leakage power of the FIFO memory array is minimized. Moreover, with the proposed dual-VT 7T SRAM cell, the FIFO memory has improved stability under ultra-low voltage supply. Simulation results show that the proposed scheme has 16% to 94% power reduction over conventional designs. The proposed scheme is implemented in UMC 90 nm CMOS technology under 0.5V supply voltage, with 1.39 uW power consumption at 5 MHz reading frequency and 200 kHz writing frequency.