We present a new method for estimating earthquake detection probabilities that avoids assumptions about earthquake occurrence, for example, the event-size distribution, and uses only empirical data: phase data, station information, and network-specific attenuation relations. First, we determine the detection probability for each station as a function of magnitude and hypocentral distance, using data from past earthquakes. Second, we combine the detection probabilities of stations using a basic combinatoric procedure to determine the probability that a hypothetical earthquake with a given size and location could escape detection. Finally, we synthesize detection-probability maps for earthquakes of particular magnitudes and probability-based completeness maps. Because the method relies only on detection probabilities of stations, it can also be used to evaluate hypothetical additions or deletions of stations as well as scenario computations of a network crisis. The new approach has several advantages: completeness is analyzed as a function of network properties instead of earthquake samples; thus, no event-size distribution is assumed. Estimating completeness is becoming possible in regions of sparse data where methods based on parametric earthquake catalogs fail. We find that the catalog of the Southern California Seismic Network (SCSN) has, for most of the region, a lower magnitude of completeness than that computed using traditional techniques, although in some places traditional techniques provide lower estimates. The network reliably records earthquakes smaller than magnitude 1.0 in some places and 1.0 in the seismically active regions. However, it does not achieve the desired completeness of magnitude ML 1.8 everywhere in its authoritative region. A complete detection is achieved at ML 3.4 in the entire authoritative region; thus, at the boundaries, earthquakes as large as ML 3.3 might escape detection.