We theoretically consider the ubiquitous soft gap measured in the tunneling conductance of semiconductor-superconductor hybrid structures, in which recently observed signatures of elusive Majorana bound states have created much excitement. We systematically study the effects of magnetic and nonmagnetic disorder, temperature, dissipative Cooper pair breaking, and interface inhomogeneity, which could lead to a soft gap. We find that interface inhomogeneity with moderate dissipation is the only viable mechanism that is consistent with the experimental observations. Our work indicates that improving the quality of the superconductor-semiconductor interface should result in a harder induced gap.