Long-term memory is a feature observed in systems ranging from neural networks to epidemiological models. The memory in such systems is usually modeled by the time delay. Furthermore, the nonlocal operators, such as the “fractional order difference,” can also have a long-time memory. Therefore, the fractional difference equations with delay are an appropriate model in a range of systems. Even so, there are not many detailed studies available related to the stability analysis of fractional order systems with delay. In this work, we derive the stability conditions for linear fractional difference equations with an arbitrary delay τ and even for systems with distributed delay. We carry out a detailed stability analysis for the cases of single delay with τ=1 and τ=2. The results are extended to nonlinear maps. The formalism can be easily extended to multiple time delays.