We study one-dimensional spinless fermions with random interactions, but without any on-site disorder. We find that random interactions generically stabilize a many-body localized phase, in spite of the completely extended single-particle degrees of freedom. In the large randomness limit, we construct "bubble-neck" eigenstates having a universal area-law entanglement entropy on average, with the number of volume-law states being exponentially suppressed. We argue that this statistical localization is beyond the phenomenological local-integrals-of-motion description of many-body localization. With exact diagonalization, we confirm the robustness of the many-body localized phase at finite randomness by investigating eigenstate properties such as level statistics, entanglement/participation entropies, and nonergodic quantum dynamics. At weak random interactions, the system develops a thermalization transition when the single-particle hopping becomes dominant.