Rocks on the floor of Gusev crater are basalts of uniform composition and mineralogy. Olivine, the only mineral to have been identified or inferred from data by all instruments on the Spirit rover, is especially abundant in these rocks. These picritic basalts are similar in many respects to certain Martian meteorites (olivine-phyric shergottites). The olivine megacrysts in both have intermediate compositions, with modal abundances ranging up to 20--30%. Associated minerals in both include low-calcium and high-calcium pyroxenes, plagioclase of intermediate composition, iron-titanium-chromium oxides, and phosphate. These rocks also share minor element trends, reflected in their nickel-magnesium and chromium-magnesium ratios. Gusev basalts and shergottites appear to have formed from primitive magmas produced by melting an undepleted mantle at depth and erupted without significant fractionation. However, apparent differences between Gusev rocks and shergottites in their ages, plagioclase abundances, and volatile contents preclude direct correlation. Orbital determinations of global olivine distribution and compositions by thermal emission spectroscopy suggest that olivine-rich rocks may be widespread. Because weathering under acidic conditions preferentially attacks olivine and disguises such rocks beneath alteration rinds, picritic basalts formed from primitive magmas may even be a common component of the Martian crust formed during ancient and recent times.