The Mars Exploration Rover Spirit has identified five distinct rock types in the Columbia Hills of Gusev crater. Clovis Class rock is a poorly sorted clastic rock that has undergone substantial aqueous alteration. We interpret it to be aqueously altered ejecta deposits formed by impacts into basaltic materials. Wishstone Class rock is also a poorly sorted clastic rock that has a distinctive chemical composition that is high in Ti and P and low in Cr. Wishstone Class rock may be pyroclastic or impact in origin. Peace Class rock is a sedimentary material composed of ultramafic sand grains cemented by significant quantities of Mg- and Ca-sulfates. Peace Class rock may have formed when water briefly saturated the ultramafic sands and evaporated to allow precipitation of the sulfates. Watchtower Class rocks are similar chemically to Wishstone Class rocks and have undergone widely varying degrees of near-isochemical aqueous alteration. They may also be ejecta deposits, formed by impacts into Wishstone-rich materials and altered by small amounts of water. Backstay Class rocks are basalt/trachybasalt lavas that were emplaced in the Columbia Hills after the other rock classes were, either as impact ejecta or by localized volcanic activity. The geologic record preserved in the rocks of the Columbia Hills reveals a period very early in Martian history in which volcanic materials were widespread, impact was a dominant process, and water was commonly present.