At ambient pressure, BiTeI exhibits a giant Rashba splitting of the bulk electronic bands. At low pressures, BiTeI undergoes a transition from trivial insulator to topological insulator. At still higher pressures, two structural transitions are known to occur. We have carried out a series of electrical resistivity and AC magnetic susceptibility measurements on BiTeI at pressure up to similar to 40 GPa in an effort to characterize the properties of the high-pressure phases. A previous calculation found that the high-pressure orthorhombic P4/nmm structure BiTeI is a metal. We find that this structure is superconducting with T-c values as high as 6 K. AC magnetic susceptibility measurements support the bulk nature of the superconductivity. Using electronic structure and phonon calculations, we compute Tc and find that our data is consistent with phonon-mediated superconductivity.