The first bridge at the site was opened in 1754, funded by public subscription. It had six arches, and replaced a ferry which was dangerous during times of bad weather and limited the volume of traffic that could pass through the town. An arch collapsed in 1756, killing 6 people. The bridge was repaired, but a storm on 25 October 1797 caused damage to the foundations of the centre arches, and the weakened structure collapsed into the river the following day.
John Rennie engineered the replacement bridge, which was built between 1800 and 1803, but he had been considering the design since 1798. It was his first major road bridge, and he gave exacting instructions for its construction, advising the trustees to build deep foundations by day labour instead of contract. The piers were sunk into the bedrock to a depth of 7 feet (2.1 m) using cofferdams, this level being around 15 feet (4.6 m) below low water. The cofferdams were kept dry by a pump driven by a water wheel on the south bank of the river.
The replacement bridge cost GB£12,876, part of which was funded by a government loan. This money was repaid by collecting tolls, which were meant to be collected only until the cost of construction had been repaid, but in 1825 the right to collect tolls was let at GB£900 per year, making the bridge extremely profitable. The collection of tolls continued until 1854, when there were riots protesting the failure of the trust that ran the bridge to publish accounts. Soldiers were called from Edinburgh to restore order, but no ringleaders were caught and the collection of tolls was abandoned later that year.
The bridge was repointed in 1921. In 1956, it was proposed that the bridge be widened, but the Fine Art Commission protested on the grounds that it would upset the architecture of the bridge. By the 1980s the parapets were both leaning outwards, and work was undertaken in 1981 on the upstream side and 1985 on the downstream side to rectify this by demolishing each parapet and rebuilding it plumb. In 1993, a fire engine crashed through the parapet whilst en route to an incident, resulting in the death of the driver.
The Kelso Bridge has five elliptical arches of 72 feet (22 m) span and 10 feet (3.0 m) rise, and is 24 feet (7.3 m) wide between the parapets. A pair of engaged Doric columns rises from the semicircular cutwaters on each of the piers. The high approach at the south end meant that to keep the deck level, as was Rennie's style, an embankment had to be built at the north end. The design of the Kelso Bridge inspired Rennie's design of the Waterloo Bridge in London.
The bridge carries the A699 public road between the north and south of the town. Downstream from the Kelso Bridge is Hunter's Bridge, a concrete viaduct opened in 1998 to direct traffic away from the centre of Kelso.