Two miles (3.2 km) east of here, SH-31B branches off, connecting the main highway with the town of Olney.

Leaving Coalgate, SH-31 turns north at SH-131, traveling 22 miles (35 km) to its junction with SH-31A, which connects with US-270 at Stuart.

SH-31 then sets off to the northeast, passing through Krebs, and crossing the south arm of Lake Eufaula.

At Kinta, SH-2 turns north, and SH-31 continues east, with a short dogleg concurrency with SH-82 at Lequire.

Continuing on to the east, SH-31 serves as the southern terminus for SH-26 at McCurtain, then passes through Bokoshe before terminating at US-59/US-271, two miles (3 km) north of Panama.