SH-58 was first commissioned some time between March 1, 1930, and December 1, 1931. The original extent of the route was much shorter than the present highway. In 1931, SH-58 was a dirt road extending from SH-8 east of Fairview north to Ringwood. Prior to receiving the SH-58 designation, this section of road was part of
US-164 and the first
SH-13. On May 29, 1930,
AASHO approved an extension of US-60 that replaced US-164. When US-60 replaced US-164 through the area, it was changed to the more westerly route it takes in the present day. The section of old U.S. highway that no longer had a designation became SH-58. The highway was extended to the south, replacing
SH-44, to Canton on March 29, 1937. SH-58 was extended north to the Kansas state line sometime between April 1937 and April 1938. This final extension brought SH-58's northern section to its present-day termini, and no major changes to the northern section have occurred since. SH-58's southern section was first established on October 16, 1945, when
SH-54 was given a new alignment further to the west; its old alignment was redesignated as SH-58. The original routing of SH-58's southern section began at
US-277 in
Cyril, continued west through
Apache, and turned north at the present-day western intersection with SH-19. SH-58 continued north along its present alignment to Hydro, where it ended at
US-66/
SH-1. In 1955, SH-19 was established through southern Caddo County, taking over the east–west section of SH-58. Thus, SH-58 was truncated to where it intersected with SH-19 (the present day western end of their concurrency). SH-58 was extended to its present terminus north of Hydro the next year. The highway was further extended in 1964, bringing the southern terminus to its present location near Medicine Park. No further routing changes have occurred since then. ==SH-58A==