A method to generate an all-optical flip-flop is proposed and experimentally demonstrated based on dynamic Brillouin gratings (DBGs) in polarization maintaining fibers. In a fiber with sufficiently uniform birefringence, this flip-flop can provide extremely long storage times and ultra-wide bandwidth. The experimental results demonstrate an all-optical flip-flop operation using phase-modulated pulses of 300 ps and a 1 m long DBG. This has led to a time-bandwidth product of ∼30, being in this proof-of-concept setup mainly limited by the relatively low bandwidth of the used pulses and the short fiber length.