To investigate the early history of olivine from the Main-Group pallasites Brahin and Brenham, we have spatially mapped their trace-element distributions using laser-ablation inductively-coupled-plasma mass spectrometry (LA-ICP-MS). Brahin olivine interiors contain ~100-200 μm patches enriched in Cr, Al, Ti, V, Sc and Ga, separated by linear enrichments of P; these structures bear no relation to current crystal morphologies. Rather, cross-cutting relationships suggest they predate olivine-metal mixing. Brenham olivine also has internal variations for these elements. By contrast, Ni and Co concentrations in olivine from both meteorites decrease near crystal margins, as expected for freezing-in of profiles formed during diffusive re-equilibration with metal during cooling. Brenham olivine also has decreasing Al, Cr and Ti near the margin. Correlations between concentrations of Cr and Al exist for individual Brahin olivine grains, but do not hold over multiple grains, indicating a heterogeneous precursor. Al and Ti are correlated over multiple grains in Brahin, interpreted as Ti cations decorating pre-existing Al-defects. In Brenham olivine, similar geochemical trends exist, but the Cr-Al relationship probably represents both grain margin effects and pre-existing internal heterogeneity.The preservation of structure for elements which are normally fast diffusers in olivine hinges on coupled substitutions involving Al, which along with P diffuses much more slowly than most other elements under some conditions. Al concentrations in olivine are low and variable (3-33 ppm) which is inconsistent with crystallisation from a normal silicate melt; Al-in-olivine thermometers indicate that pallasite olivine was formed in a low-temperature environment. Following its delivery to the magma ocean/core-mantle boundary, Al-P systematics were not substantially modified. Assuming diffusivities for Al and P that are similar to Si (since they reside in the same crystallographic site) and temperatures of 1600-1650 K (from the melting point of the metal and the absence of orthopyroxene in pallasites) an upper limit on the residence time of pallasite olivine of ~1 Ma can be inferred by the persistence of trace element detail over scales of 100 μm. Following the olivine-metal mixing event, homogeneous Ni and Co distributions were modified by diffusion; Cr and V were partially modified; Al and P were essentially unchanged.