Real Balompédica Linense's original date of founding is somewhat disputed with the club and current Chairman believing it to have been formed on September 12, 1912. This is now commonly accepted due to a document of the Andalusia Football Federation which had this date in its official yearbook. However prior to this document being rediscovered it was believed to have been founded in 1921 when it was registered and started competing. The club was a merger of several amateur clubs from La Línea and possibly Gibraltar. On the 8th of December 1921 Balompédica Linense played and won its debut match, played against Club Racing Santander. 9 months later, on September 5, 1922 the club joined the South Regional Federation. In the same year the club also added the distinction of Real to its name, thus creating the present name of Real Balompédica Linense. For the first years of competition the club played its matches at the Aurora Sports Field. As the club began participation in official competitions it became necessary for it to have a custom field. Thus the club opened the San Bernardo Estadio, playing its first match at the ground on the 17th of October 1926, being defeated 2-1 by FC Malagueno.
The club started its life jumping between the Regional División and Tercera División. The club's fortunes began to change however in the 1950s, when the club gained promotion to the Segunda División in the 1949-50 season. The club managed to avoid relegation with a respectable 12th place finish in its first season in the Spanish second flight. This season proved to be the first of six straight seasons in the Segunda División for Balona, ending with relegations to the Tercera División at the end of the 1954/55 season.
Following its stint in the second flight, Balona returned to the Tercera División where it stayed for 28 years, bar one in the 1976/77 season where it returned to the Regional División. Following several consistent high finishing seasons the 1982/3 season proved a success for Balona with it coming first in the Tercera División and gaining promotion to the recently created Segunda División B. The club had another extended period in a single league, this time being 10 years. During these ten years the club managed a second place finish in the 1985/86 season, however this wasn't enough to see it gain promotion to the Segunda División.
Despite the club's high finishes in some seasons throughout its initial 10 year stint in the Segunda División it was relegated in the 1992/93 season back to the Tercera División. The club stayed in the Tercera División for another 6 seasons before, again, gaining promotion to the Segunda División B following a first placed finish in the División due to a last match of the season win. This proved to be the start of the club having a period of short stints in the Tercera and Segunda B, with 3 seasons in the Segunda B (1999/00 - 2001/02), 6 in the Tercera (02/03- 2007/08), 1 in the Segunda B (2008/09) and 2 in the Tercera (2009/10, 2010/11). A notable occurrence during these string of promotions and relegations was the arrival of Alfredo Gallardo as the Chairman of the club in the 2002/03 season. Gallardo still holds this position and on his arrival also brought in several local businessmen to help fund the club. A second notable occurrence was in the 2007/08 season with the club going through qualifications for promotion after a third place finish. This saw the club defeat CD Anguiano due to the away goals rule before having a dramatic conclusion to the qualification with a double tie against CD Mirandes. The first match played in La Linea de la Concepcion ended in a 1-1 result meaning CD Mirandes were ahead on the away goals rule. However the result was completely turned around on the return leg at Estadio Municipal de Anduva, Miranda de Ebro with the match ending 3-3, and thus Balona winning promotion on the away goal rule. The club currently is in the Segunda B following a first placed finish in the Tercera División in 2010/11. The club achieved a high finish, second, the season following its promotion and backed this up with a solid sixth placed finish in the 2012/13 season.