The Elephant Random Walk (ERW), first introduced by Schütz and Trimper (2004), is a one-dimensional simple random walk on $ \mathbb{Z} $ having a memory about the whole past. We study the Shark Random Swim, a random walk whose steps are $ α$-stable distributed with memory about the whole past. In contrast with the ERW, the steps of the Shark Random Swim have a heavy tailed distribution. Our aim in this work is to study the impact of the heavy tailed step distributions on the asymptotic behavior of the random walk. We shall see that, as for the ERW, the asymptotic behavior of the Shark Random Swim depends on its memory parameter $ p $, and that a phase transition can be observed at the critical value $ p=\frac{1}α $.