Syndabockar för Colombia blev Mateus Uribe och Carlos Bacca som missade sina straffar. Jordan Henderson missade för England och han får tacka målvakten Jordan Pickford som räddade Baccas avslutande innan Eric Dier avgjorde.
Det var en match som präglades av griniga avblåsningar och många varningar.
Första halvleks bästa chans hade Harry Kane, som efter en kvarts spel nickade strax över.
I slutet halvleken utbröt ett bråk mellan lagen i samband med en engelsk frispark. Den colombianska mittfältaren Wilmer Barrios skallade Henderson i bröstet och fick ett gult kort som gjorde att han hade missat en eventuell Sverige-match.
Kane leder skytteligan
Efter paus fortsatte kampen på planen och i den 57:e minuten rev Carlos Sanchez ner Kane i straffområdet.
Tottenham-anfallaren tog sedan straffen själv och därmed var ställningen 1-0. Målet var Kanes sjätte i VM och han leder därmed skytteligan, två bollar före Belgiens Romelu Lukaku och den redan utslagna Cristiano Ronaldo.
Sanchez har haft ett riktigt tungt VM då hans tidiga utvisning mot Japan i premiären var en stor orsak till förlusten där.
Med tio minuter kvar att spela hade Juan Cuadrado ett jätteläge att kvittera, men bollen gick rejält över.
Kvittering på stopptid
På stopptid kom sedan kvitteringen. Först sköt inhopparen Mateus Uribe ett skott som Jordan Pickford räddade jättesnyggt till hörna, men på den hörnan nickade sedan Yerry Mina in kvitteringen. Mittbacken, som representerar Barcelona, har nu gjort mål i tre raka matcher.
I förlängningen var det sedan Englands Danny Rose som var närmast att hitta målet, men hans avslut från liten vinkel smet knappt förbi stopen. I straffläggningen var England alltså vassare och segern på straffar är alltså deras första i VM genom tiderna. Den enda i mästerskapssammanhang kom i EM 1996 mot Spanien.