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 90nm CMOS technology under 0.5V supply voltage, with 1.39uW power consumption at 5MHz reading frequency and 200kHz writing frequency.