Lumbermen and trappers first set up camps in the area in the 1810s. The first settlers came to what is now Caribou in the 1820s. Between 1838 and 1840, the undeclared Aroostook War flared between the United States and Canada, and the Battle of Caribou occurred in December 1838. The dispute over the international boundary delayed settlement of the area until after the signing of the Webster-Ashburton Treaty in 1842. With peace restored, European settlers arrived in gradually-increasing numbers beginning in 1843. From Eaton Plantation and part of half-township H, Caribou was incorporated in 1859 as the town of Lyndon on April 5. In 1869, it annexed Eaton, Sheridan and Forestville plantations. On February 26 of that year its name was changed to Caribou, only to revert to Lyndon on March 9. On February 8, 1877, Caribou was finally confirmed as the town's permanent name. Two enduring mysteries are the reason for the original name of Lyndon, and the reasons for the town's name being subsequently changed back and forth between Lyndon and Caribou. Caribou was the "jumping off" point for a large influx of settlers who immigrated directly from Sweden in 1870-1871, and settled the nearby "Swedish colony." The small town grew throughout the late 19th century, and with the coming of the Bangor and Aroostook Railroad in the 1890s, agricultural exports exploded. This began a boom period which lasted well into the 1960s. Caribou became the largest potato shipping hub in the world, and had many related industries.
Nearby to the northeast, Loring Air Force Base opened in the early 1950s near Limestone, with bomber and tanker aircraft of the Strategic Air Command. It provided a major economic boost to the area, with construction starting in 1947 on "Limestone Army Air Field." Caribou was incorporated as a city in 1967 on February 23, but the area's boom period leveled off in the 1970s as a result of difficulties in its traditional potato industry. That, along with closure of the base in 1994, contributed to a decline in population in the 1980s and 1990s.
In September 1984, Caribou was the lift-off location of the first successful solo balloon crossing of the Atlantic Ocean by Colonel Joseph Kittinger. This flight is memorialized at the Rosie O'Grady Balloon of Peace Park one mile (1.6 km) south of the city on Main Street. This site includes a large replica of Kittinger's balloon.
The Caribou Public Library is a Carnegie library. Designed in the Romanesque Revival style by local architect Schuyler C. Page, it was built in 1911-1912 with a $10,000 grant from industrialist Andrew Carnegie.