Keflavík first played league football when the team joined the newly formed second division in 1956. Keflavík was promoted in 1957 and played in the top flight from 1958–60. The team returned to the second division in 1961 but were promoted again the following year. After narrowly avoiding relegation in 1963 Keflavík won its first title in 1964. The team also won the title in 1969, 1971 and 1973. Since then the team has mostly played in Iceland's top division, Úrvalsdeild, with three spells in the second tier (1981, 1990–92 and 2003).
The Icelandic FA Cup was established in 1960 and Keflavík entered from the beginning. The team's first cup game ended in a 0–6 defeat by ÍA. Keflavík reached the semi-final of the competition the next three years and had reached seven semis before playing for the first time in the final in 1973. That game ended in a 1–2 defeat by Fram. In 1975 Keflavík won the cup for the first time, beating ÍA by a single goal. The team reached the final again in 1982, 1985, 1988 and 1993 but lost each time. The duck was finally broken in 1997 when ÍBV were beaten in a penalty-shootout in a replay. Keflavík won the FA Cup again in 2004 and 2006, first by beating KA 3–0 and then KR 2–0.
Keflavík played its first European game in 1965 after becoming champions the previous year. The team were drawn against Hungarian side Ferencváros in the European Cup. The Hungarians won 9–1 and 4–1 for a 13–2 aggregate win. In the early 70's Keflavík were the envy of other Icelandic teams when they were drawn against several top sides, including Everton in 1970, Tottenham Hotspur in 1971 and Real Madrid in 1972. Keflavík's first win in European competition came against Swedish side Kalmar FF in the 1979–80 UEFA Cup. Keflavík won the home match 1–0 and progressed to the second round for the first time, winning on away goals. Keflavík played in the UEFA Europa League in 2009–10 after finishing 2nd in the Icelandic Premier League in 2008 and lost to Maltese club Valletta with the aggregate favoring the Maltese 5–2.
The Keflavík football team originally played in black shirts and white shorts. In 1973, the team changed its strip to yellow shirts and blue shorts. One reason given for the change was the memory of the team's first European away match, against Ferencváros in Budapest. The Keflavík players were playing in floodlights for the first time and had trouble spotting each other in their black shirts. Another reason was the fact that at the time all referees wore black so the black shirts of Keflavík were often frowned upon by referees and officials. The team wore the yellow and blue strip through 1980s, usually with an all-white change strip. At the start of the 1990 season, it was decided to revert to the team's original colours. The team had been relegated the previous season and the change was considered a fresh start and a throwback to the glory days of 1960s and early 1970's. The black and white strip was used for six years with white shirts and black shorts as an alternative. In 1995 the board of Keflavík ÍF decided that the club's colours would be dark blue, white and red and that all teams representing the club should use dark blue as the main colour of their uniforms and clothing. At the start of the 1996 season the football team started to wear a dark blue strip with white stripes. The away strip is all red with white stripes.