In this paper, we introduce the elephant random walk (ERW) with memory consisting of randomly selected steps from its history. It is a time-changed variant of the standard elephant random walk with memory consisting of its full history. At each time point, the time changing component is the composition of two uniformly distributed independent random variables with support over all the past steps. Several conditional distributional properties including the conditional mean increments and conditional displacement of ERW with random memory are obtained. Using these conditional results, we derive the recursive and explicit expressions for the mean increments and mean displacement of the walk.