The freeway enters Gallup 20 miles (32 km) later, paralleling the Burlington Northern Santa Fe Railway's southern transcontinental mainline.

Near the interchange with State Road 6 (NM 6), the railway line that accompanies much of the route from the Arizona border diverts to the south while the freeway turns east by northeast toward Albuquerque.

From Laguna to the Route 66 Casino, I-40 has at-grade intersections with a number of ranch access roads in violation of Interstate Highway standards.

At Tucumcari, I-40 diverges from US 54 and turns eastward and skirts the northern edge of San Jon before reaching the Texas state line at Glenrio.

By the end of the 1960s, most rural sections of I-40 were completed across the state with the largest exception being a 40-mile (64 km) stretch east of Tucumcari to the Texas border at Glenrio, where traffic was diverted to the old US 66.

However, aside from a few small villages, such as Montoya, Newkirk, and Cuervo in the eastern portion of the state and Laguna, Budville, and Cubero to the west, no major bypasses had been entirely completed in New Mexico, so traffic was still diverted over the US 66 routes through each of those cities.

Other bypasses were completed around various cities through the state, including San Jon (1976) and Tucumcari (1981),[4] Santa Rosa (1972), Moriarty (1973), Grants (1974), and Gallup (1980).