Ustikolina has been inhabited since the ancient period, as evidenced by the foundings of Roman coins made of bronze and copper dating from the period between the second and fourth centuries. In addition, Roman tegula-bricks and Roman ceramics were found. Near Cvilin, archaeologists found the remains of Roman villas with floor mosaics, bronze dishes and tombstones with Roman inscriptions. It got its name from the river Kolina, so the name Ustikolina means "Mouth of the Kolina". Ustikolina is first mentioned in historical sources in the Chronicles of Pope Dukljanin, where it is recorded that the Serbian emperor Časlav 895-896 defeated the Hungarians (Bosnia was a vassal of Hungary during this period) on the Cvilinski field near Ustikolina. In the local surroundings of Ustikolina there is a necropolis of stećci, which indicates that this area was also inhabited in the Middle Ages by the Bosnian Christians. In Ustikolina the first known mosque in Bosnia and Herzegovina was built in 1443 or 1448, the original builder is unknown but it was later on named after Turhan Emin-beg. The mosque was completely destroyed during World War II, rebuilt after and again destroyed during the Bosnian War. It was rebuilt again in 2007, the original foundations of the mosque have been lost.^[3]

According to the 2013 census, its population was 882.^[4]