We consider the problem of randomly selecting $s$ different $m$-element subsets of $\{1,...,k\}$. The only known lower bound for this problem is the trivial $\Omega (sm)$. The best two previously known solutions are of time $O(sm^2)$ and $O(s(k+m))$, respectively. We present an algorithm for $k>s+m$ whose time complexity is $O(sm\log m + s^2)$, and whose space requirement is $O(sm)$. For $s\leq m$ this algorithm is almost optimal. It has an added advantage over the $O(sm^2)$ algorithm in that it operates in a conventional model of computation. It has a clear advantage over the $O(s(k+m))$ algorithm for large $k$ (in fact that latter algorithm also has space complexity $O(k+m)$). (joint work with Imanuel Dar)