Fountain was born on Staten Island, New York, on October 23, 1838, to Solomon Jennings and his wife Catherine de la Fontaine. He went to California as a young man and began calling himself by an Anglicised version of his mother's family name. (Accounts differ as to why he did so.) He studied law in California, and was admitted to the bar in 1860. Working as a reporter for the Sacramento Union, Fountain travelled to Nicaragua in 1860 to cover the filibustering (colonizing) expedition of William Walker. Angering Walker by his reports, Fountain was arrested and sentenced to be shot. However, he escaped and returned to California.
In August 1861, during the American Civil War, Fountain enlisted in the Company E of the 1st California Infantry Regiment of the Union Army and was elected first sergeant of his company. He took part in the 1862 Union recapture of the New Mexico Territory as a member of the California Column. In October 1862, he married Mariana Pérez of Mesilla. They would become the parents of four sons and two daughters. Later commissioned a second lieutenant, he was discharged on August 31, 1864. Fountain almost immediately joined the New Mexico volunteers because of the ongoing Indian wars. In June 1865, he was seriously wounded while pursuing hostile Apaches. He spent a night trapped under his dead horse, with a bullet in his thigh, an arrow in his forearm, and another arrow in his shoulder. On his recovery, he was discharged as a brevet captain.
Fountain settled in El Paso, Texas, working for the United States Property Commission, which investigated and disposed of former Confederate property. He was then made the customs collector for the El Paso region. He was next appointed an election judge, and finally became the assessor and collector of internal revenue for the Western District of Texas.
In November 1869, Fountain won a seat as a Republican in the Texas Senate, serving in the Twelfth and Thirteenth Texas Legislatures. He was elected as president pro tempore during the second session of the Twelfth Legislature and served as Lieutenant Governor ex officio at the same time, as the office was vacant. His most notable accomplishment was pushing through the bill that re-established the Texas Rangers, which had been abolished after the Civil War.
Fountain's Radical Republican views angered Texas Democrats, and he was challenged to several duels, killing at least one man, Frank Williams. At the time of Fountain's disappearance, he was prosecuting suspected cattle rustlers, specifically Oliver M. Lee, and he found himself at odds with Lee's associate, the attorney Albert Fall.
In 1873, Fountain decided to move back to his wife's home of Mesilla, New Mexico. He became a lawyer there, using his fluent Spanish to good advantage in jury trials. He was appointed assistant district attorney and also served as probate judge and a deputy court clerk. In 1877, he founded a newspaper, the Mesilla Valley Independent, which was issued in both English and Spanish.
Fountain practiced law in Mesilla and his most famous client was Billy the Kid. Fountain lost the 1881 case, and Billy the Kid was convicted of murder despite the evidence, though he escaped from jail. Fountain was a leading figure in the Republican Party in New Mexico, serving a term in the state legislature.
In 1888, Fountain was elected to the New Mexico Territorial Legislature, defeating his enemy Albert Bacon Fall.
On February 1, 1896, Fountain and his eight-year-old son Henry disappeared near White Sands on the way to their home in Mesilla. They were returning from Lincoln, New Mexico, where Fountain had been assisting the prosecution in bringing charges against Oliver M. Lee and William McNew. All that was found at the site of the disappearance were Fountain's buckboard wagon, several empty cartridge cases, his cravat and papers, and two pools of blood. The only sign of Henry Fountain was a blood-soaked handkerchief with two powder-blackened coins, the handkerchief still carefully knotted in one corner. Missing were the victims' bodies, a blanket, a quilt, and Fountain's Winchester rifle.
Some speculated that outlaw "Black Jack" Ketchum and his gang were involved. Most, however, were convinced the disappearances could be attributed to Lee, a noted rancher, land developer, and a part-time Deputy U.S. Marshal. Lee's employees Jim Gililland and William McNew were also suspected of involvement. Lee and Gililland were pursued by lawman Pat Garrett and a posse, who engaged them in a gunfight near Alamogordo. However, after Deputy Sheriff Kent Kearney was mortally wounded, Garrett and his posse withdrew. Lee and Gililland would later negotiate their surrender to others. They were defended by Albert Bacon Fall, who years later would become the first United States presidential cabinet member convicted of a felony and sentenced to prison during the Teapot Dome Scandal. The accused were acquitted due to a lack of evidence.
Fountain was a powerful rival to land owners Fall and Lee. Fall was also known to hate Fountain as a political rival, just as Fountain hated Fall. Fall's association with Lee began when he had defended Lee in a criminal case. Fountain had repeatedly challenged Fall and his men in the courts and the political arena.
As the bodies of Fountain and his son were never found, the prosecution was greatly hampered. No one was ever charged with the murder of Albert Fountain. Lee and his employees, McNew and Gilliland, were tried for the murder of Henry Fountain. Charges also were never filed for the death of Deputy Sheriff Kearney. The charges against McNew were dismissed, while Lee and Gililland were both acquitted.
Memorials to both Albert Jennings Fountain and his son are in the Masonic Cemetery in Las Cruces, though their actual burial site remains a mystery.
The Fountain family ran the Mesilla Valley Opera House and built the Fountain Theatre in Old Mesilla near Las Cruces, New Mexico. The theater was rebuilt in 1905 for stage plays and musical concerts, and is the oldest motion picture theater in New Mexico. The Fountain Theatre is currently operated by the Mesilla Valley Film Society. The interior decoration includes murals of Albert Jennings Fountain painted by his son Albert, Jr.
Fountain's disappearance was dramatized in the 2013 film Among the Dust of Thieves.