Abstract: We investigate important combinatorial and algorithmic properties of $G_{n, m, p}$ random intersection graphs. In particular, we prove that with high probability (a) random intersection graphs are expanders, (b) random walks on such graphs are ``rapidly mixing" (in particular they mix in logarithmic time) and (c) the cover time of random walks on such graphs is optimal (i.e. it is $\Theta(n \log{n})$). All results are proved for $p$ very close to the connectivity threshold and for the interesting, non-trivial range where random intersection graphs differ from classical $G_{n, p}$ random graphs.