Combining density functional theory and the nonequilibrium Green's function method, we investigate the thermoelectric properties of thin GaAs nanowires (NWs). After identifying the most stable structures for GaAs NWs, either in wurtzite (wz) or zinc blende (zb) stacking, we present a systematic analysis on the thermoelectric properties of these NWs and their dependence on stacking type (wz or zb), size of NWs, and temperature. Although bulk GaAs is a well-known poor thermoelectric material, the thermoelectric figure of merit, ZT, is significantly enhanced in thin GaAs NWs. Typically, the room temperature ZT of a 1.1 nm-diameter GaAs NW reaches as high as 1.34, exhibiting more than 100-fold improvement over the bulk counterpart, which is attributed to both the reduced thermal conduction and enhanced power factor in thin NWs. Adopting their unique electronic characteristics, further enhancement is possible through surface engineering, for example, the introduction of surface roughness or dopants.