We present an efficient algorithm for generating an n x n nonsingular matrix uniformly over a finite field. This algorithm is useful for several cryptographic and checking applications. Over GF[2] our algorithm runs in expected time M(n) + O(nsquared), where M(n) is the time needed to multiply two n x n matrices, and the expected number of random bits it uses is nsquared + 3. (Over other finite fields we use nsquared + O(1) random field elements on average.) This is more efficient than the standard method for solving this problem, both in terms of expected running time and the expected number of random bits used. The standard method is to generate random n x n matrices until we produce one with nonzero determinant. In contrast, our technique directly produces a random matrix guaranteed to have non-zero determinant. We also introduce efficient algorithms for related problems such as uniformly generating singular matrices or matrices with fixed determinant.