A scenery is a coloring xi of the integers. Let {S-t}(t >= 0) be a recurrent random walk on the integers. Observing the scenery xi along the path of this random walk, one sees the color chi(t) := xi(S-t) at time t. The scenery reconstruction problem is concerned with recovering the scenery xi, given only the sequence of observations chi := (chi(t))(t >= 0). The scenery reconstruction methods presented to date require the random walk to have bounded increments. Here, we present a new approach for random walks with unbounded increments which works when the tail of the increment distribution decays exponentially fast enough and the scenery has five colors.