This study examines the three-dimensional velocity structure in a 60- by 80-km region containing the Parkfield segment of the San Andreas fault. We use local earthquake and shot P arrival times in an iterative simultaneous inversion for velocity and hypocentral parameters. Using the three-dimensional model, we relocated 5251 events that occurred from 1969 to 1991, as well as the 1966 aftershocks, and computed 664 fault plane solutions. The San Andreas fault (SAF), characterized by a sharp across-fault velocity gradient, is the primary feature in the velocity solution. There is a 5--20% lateral change in velocity over a 4-km width, the contrast being sharper where there is better resolution. The model also shows significant variations in the velocity and in the complexity of the velocity patterns along the SAF. The largest across fault velocity difference is below Middle Mountain, where a large volume of low-velocity material impinges on the SAF from the northeast. This material is inferred to be overpressured and may be key to understanding the unusual behavior in the Parkfield preparation zone. A 20-km-long high-velocity slice is imaged northeast of the SAF near Gold Hill. Its along-fault length corresponds to the length of the maximum slip in 1966. The relocated seismicity shows that the San Andreas fault is a planar vertical fault zone at seismogenic depths. Ninety percent of the fault plane solutions that are on, or near, the SAF were right-lateral strike-slip on subvertical fault planes that parallel the SAF. Thus the surface fault complexities do not appear to extend to depth and therefore do not explain the rupture character at Parkfield. At Parkfield, variations in material properties play a key role in fault segmentation and deformation style. Our observations suggest that there may be a general relation between increasing velocity and increasing ability of the rocks to store strain energy and release it as brittle failure.