A grid search is used to estimate average crustal thickness and shear wave velocity structure beneath 12 three-component broadband seismic stations in the Middle East, North Africa, and nearby regions. The crustal thickness in these regions is found to vary from a minimum of 8.0 +/- 1.5 km in East Africa (Afar) region to possibly a maximum of 64 +/- 4.8 km in the lesser Caucasus. Stations located within the stable African platform indicate a crustal thickness of about 40 km. Teleseismic three-component waveform data produced by 165 earthquakes are used to create receiver function stacks for each station. Using a grid search, we have solved for the optimal and most simple shear velocity models beneath all 12 stations. Unlike other techniques (linearized least squares or forward modeling), the grid search methodology guarantees that we solve for the global minimum within our defined model parameter space. Using the grid search, we also qualitatively estimate the least number of layers required to model the observed receiver functions' major seismic phases (e.g., PSMoho). A jackknife error estimation method is used to test the stability of our receiver function inversions for all 12 stations in the region that had recorded a sufficient number of high-quality broadband teleseismic waveforms. Five of the 12 estimates of crustal thickness are consistent with what is known of crustal structure from prior geophysical work. Furthermore, the remaining seven estimates of crustal structure are in regions for which previously there were few or no data about crustal thickness.