To kill Escherichia coli, toxic proteins, called colicins, pass through the permeability barrier created by the outer membrane (OM) of the bacterial cell envelope. We consider a variety of different colicins, including A, B, D, E1, E3, Ia, M and N, that penetrate through the porins OmpF, FepA, BtuB, Cir and FhuA, to subsequently interact with a few targets in the periplasm, including TolA, TolB, TolC and TonB. We review the mechanisms, demonstrated and postulated, by which such toxins enter bacterial cells, from the initial binding stage on the cell surface to the internalization reaction through the OM bilayer. Our discussions endeavor to answer two main questions: what is the origin of colicin-binding affinity and specificity, and after adsorption to OM porins, do colicin polypeptides translocate through porin channels, or enter by another, currently unknown pathway?