We implement the Wang-Landau algorithm in the context of SU(N) lattice gauge theories. We study the quenched, reduced version of the lattice theory and calculate its density of states for N=20, 30, 40, 50. We introduce a variant of the original algorithm in which the weight function used in the update does not asymptote to a fixed function, but rather continues to have small fluctuations that enhance tunneling. We formulate a method to evaluate the errors in the density of states, and use the result to calculate the dependence of the average action density and the specific heat on the 't Hooft coupling lambda. This allows us to locate the coupling lambda(t) at which a strongly first-order transition occurs in the system. For N=20 and 30 we compare our results with those obtained using Ferrenberg-Swendsen multihistogram reweighting and find agreement with errors of 0.2% or less. Extrapolating our results to N=infinity, we find (lambda(t))(-1)=0.3148(2). We remark on the significance of this result for the validity of quenched large-N reduction of SU(N) lattice gauge theories.