Teleseismic P-wave receiver function data and Rayleigh-wave phase velocity measurements are combined using the genetic algorithm, a global optimization technique, to model crustal structure in southern Korea. The two datasets complement each other because receiver functions are sensitive to shear-wave velocity contrasts in layered structures, while surface wave dispersion is sensitive to averages of shear-wave velocities. The genetic algorithm is more useful than linearized inversion in regions where there is little a priori information about local velocity structure because it is not sensitive to the initial model. The stability and variability of resulting crustal model parameters are quantified by using a Monte Carlo technique in specifying a suite of initial models. Depths to the Moho discontinuity in southern Korea were estimated to be 29-30 km for stations near the western coast and 33-36 km for inland stations. A well-resolved crustal low-velocity zone was inferred for some stations.