SHORT ANSWER
Physical barriers along the US-Mexico border have been erected at various points since at least 1918. Most of these, though, were short and often not maintained. The first major proposal to put up a barrier along several areas of the border was in the late 1970s during the Carter administration, the controversial Tortilla Curtain, but the proposal was scaled back after protests. A more permanent structure went up in 1991 during the Bush Sr. administration.
DETAILED ANSWER
The idea of an actual physical barrier along the US-Mexico border is not a new one, but Mexican immigrants in the first half of the 20th century were, for the most part, welcomed for the much needed cheap labour they provided. Further, much of the border was no more than a line on a map, and in some areas an uncertain one at that. Nonetheless, there were exceptions, the first of note apparently being Nogales on the Arizona - Mexico border where a shootout in 1918 left at least 24 dead.
After peace was restored, both governments agreed to build a two-mile
border fence running along the center of International Street, the
first of its kind in the area.
The fence put up after the battle. Source: The August 27, 1918
Battle of Ambos Nogales
and the First U.S.-Mexican Border Fences
During the Great Depression, there was less tolerance of immigration; witness 1936 in south west California:
Civilian Conservation Corps members began building a “high,
barbed-wire fence strung on metal poles set close together” going west
from Tecate, the intention of which was to join an apparently similar
and already existing fence that began at the Pacific Ocean and went
all the way to the Marone Valley, about eight miles west of Tecate.
This supposed fence of over 50 miles was either never completed or was simply not maintained as, in 1948, an INS official in San Ysidro observed
“At present time, with no fence worthy the name [sic], it is very easy for any alien who is turned back at the port…to cross within a short distance of the port.”
Sometime before the early 1950s, in El Paso, Texas
the U.S. erected a menacing series of barbed-wire fences and
watchtowers, reminiscent of the totalitarian European states of the
World War II era. The watchtowers were eventually removed, but the
fences remained. Their purpose was not only to keep out Mexican
immigrants, but they were also used to halt the spread of livestock
diseases and discourage the traffic of contraband.
In the 1940s, fences went up in Arizona, but these were to control the movement of Mexican cattle rather than Mexican people, the concerns being overgrazing and the spread of disease by hoofed animals. In Nogales, Arizona, little changed over the following decades according to this Mark Binelli report in Pacific Standard:
Well into the 1980s, border security in Nogales remained nominal.
Several longtime residents I met recalled the sagging chain-link
border fence running through town, easily slipped beneath if there
happened to be a long line at the customs booth. "Prior to 1995, there
were gaps all over the fence," confirmed Tony Estrada, the sheriff of
Santa Cruz County
This was despite an increase in strong rhetoric from individuals such as former CIA director William Colby who considered Mexican immigration to be a bigger threat than the Soviet Union. Others, such as LA Police Chief (1969–1978 ) Ed Davis and California Senator (1967-77) George Deukmejian also weighed in but little happened. Although polls in the 1970s showed an increase in public concern at the level of immigration, only cattlemen seemed concerned enough to do anything in terms of a physical barrier:
Disinterest in boundary enforcement issues is reflected in a 1975
report on efforts to repair the boundary fence, which attributed the
source of the effort to the San Diego Cattlemen’s Association as it
was worried about its members’ cattle wandering into Mexico.
Then, in 1977, President Jimmy Carter announced major measures aimed at decreasing the number of illegal immigrants. Included in this was an increase for the Border Patrol which, during the Carter years, led to the Tortilla Curtain
In 1977 and 1978 the U.S. Congress approved funding for even more
fencing in El Paso and other densely populated locations along the
Mexican border between Texas and California. These new fences, which
were to be strewn with razor wire to deter unwanted Mexican immigrants
from entering the country, were referred to collectively as the
“Tortilla Curtain.”
These new fences proved hugely controversial:
Mexican officials and those who resided near the border lashed out at
the United States Immigration and Naturalization Service (INS)...
Protests and riots ensued as groups such as the Coalition Against the
Fence were formed and demanded more compassion from the United States
government. The use of razor wire to deter illegal immigration was
considered inhumane and was relatively ineffective.
These protests proved to be successful along with a meeting that took
place in February 1979 between U.S. President Jimmy Carter and Mexican
President José López Portillo to discuss easing tensions along the
border. Final construction of fencing was limited in its total length
and lacked the razor wire.
"The black fence in the background — known as the "Tortilla Curtain" — was built in 1979 in an effort to keep immigrants out of El Paso." Source: The Southwest
Joseph Nevins, in Operation Gatekeeper, provides further details:
...the Carter administration proposal evolved to include two six-mile
steel fences (essentially walls) between San Ysidro and Tijuana, and
El Paso and Ciudad Juárez... many in San Diego, including members of
its U.S. Congressional delegation and the San Diego City Council,
opposed the new fence on the grounds that it was unnecessary, would
prove to be ineffective, and would hurt U.S.-Mexico relations.
Nonetheless, a 1979 poll indicated 64% of San Diego residents supported “enhanced fencing” but
support for the fence was apparently not well organized nor
mobilized....When a new fence was eventually built, it was neither
sturdier nor any more difficult to scale or cut than the one it
replaced. Within one year, there were at least twenty large holes—some
large enough for a truck to pass through—in the four miles of
already-completed new fencing
Ronald Reagan specifically rejected fences during a 1980 Presidential election debate with George Bush Snr. Reagan enacted a huge amnesty program in 1986 for illegal aliens at the same time as greatly increasing funds for border control, with much emphasis on high-tech equipment and increasing the number of agents and little emphasis on physical barriers. The focus now was the War on Drugs (a term first used by Nixon in 1975), but it’s impossible to separate immigration from this.
Despite the Tortilla Curtain incidents, the 1990 Immigration Act during the Bush Sr. presidency “allowed funds from increased penalties to be used for repairing, maintaining, and constructing border barriers” and
In 1991, the U.S. Navy built a 10-foot high wall of corrugated steel
between San Diego and Tijuana using surplus military aircraft landing
mats. The wall stretched for seven miles along the border in the Chula
Vista sector (in 1993 it was expanded to 14 miles, extending into the
Pacific Ocean) and marked a momentous upgrade from the chain-link
fences that had previously demarcated the border.
This, essentially, was the background to Operation Gatekeeper which was a long way from being the first attempt to construct a physical barrier; rather, it was a continuation of sporadic attempts over many decades to control immigration by putting up a physical obstacle.
Trump’s plan to put a wall across the entire US – Mexican border does seem to be a first from a major political figure. Not even conservative Republican presidential candidate Pat Buchanan, during his runs for President in 1992 and 1996, proposed such a plan.
Other sources:
Commentary: The futility of a Mexico-United States wall
Up Against the Wall