To investigate the performance of quantum information tasks on networks whose topology changes in time, we study the spatial search algorithm by continuous time quantum walk to find a marked node on a random temporal network. We consider a network of $n$ nodes constituted by a time-ordered sequence of Erd"os-R'enyi random graphs $G(n,p)$, where $p$ is the probability that any two given nodes are connected: after every time interval $ au$, a new graph $G(n,p)$ replaces the previous one. We prove analytically that for any given $p$, there is always a range of values of $ au$ for which the running time of the algorithm is optimal, i.e. $mathcal{O}(sqrt{n})$, even when search on the individual static graphs constituting the temporal network is sub-optimal. On the other hand, there are regimes of $ au$ where the algorithm is sub-optimal even when each of the underlying static graphs are sufficiently connected to perform optimal search on them. From this first study of quantum spatial search on a time-dependent network, it emerges that the non-trivial interplay between temporality and connectivity is key to the algorithmic performance. Moreover, our work can be extended to establish high-fidelity qubit transfer between any two nodes of the network. Overall, our findings show that one can exploit temporality to achieve optimal quantum information tasks on dynamical random networks.