We determine the probability of return for random walks on Z whose increment is given by the Fibonacci sequence. In addition we calculate the Hausdorff dimension of the set of these walks that return an infinite number of times.