In McAlester, SH-31 forms a five-mile (8 km) concurrency with US-270 and SH-1, splitting up just east of the US-69 interchange on the east side of the city. SH-31 then sets off to the northeast, passing through Krebs, and crossing the south arm of Lake Eufaula.
At Quinton, 27 miles (43 km) from McAlester, SH-31 serves as the southern terminus of SH-71, then heads east, forming a six-mile (10 km) concurrency with SH-2 to the town of Kinta. 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 though Bokoshe before terminating at US-59/US-271, two miles (3 km) north of Panama.