This paper describes the Polarization Spectroscopic Telescope Array (PolSTAR), a mission proposed to NASAs 2014 Small Explorer (SMEX) announcement of opportunity. PolSTAR measures the linear polarization of 3-50 keV (requirement; goal: 2.5-70 keV) X-rays probing the behavior of matter, radiation and the very fabric of spacetime under the extreme conditions close to the event horizons of black holes, as well as in and around magnetars and neutron stars. The PolSTAR design is based on the technology developed for the Nuclear Spectroscopic Telescope Array (NuSTAR) mission launched in June 2012. In particular, it uses the same X-ray optics, extendable telescope boom, optical bench, and CdZnTe detectors as NuSTAR. The mission has the sensitivity to measure ~1% linear polarization fractions for X-ray sources with fluxes down to ~5 mCrab. This paper describes the PolSTAR design as well as the science drivers and the potential science return.