The 1958 New Mexico A&M Aggies football team was an American football team that represented New Mexico State University in the Border Conference during the 1958 college football season. In its first year under head coach Warren B. Woodson, the team compiled a 4–6 record (1–3 against conference opponents), finished in fourth place in the conference, and was outscored by a total of 228 to 172.^[1][2]

Woodson was later inducted into the College Football Hall of Fame.

Date	Opponent	Site	Result	Attendance	Source
September 13	Trinity (TX)*	Memorial Stadium Las Cruces, NM	L 0–20
September 20	New Mexico*	Memorial Stadium Las Cruces, NM (rivalry)	L 7–16	6,500	[3]
September 26	University of Mexico*	Memorial Stadium Las Cruces, NM	W 28–14
October 4	at North Texas State*	Fouts Field Denton, TX	L 12–43		[4]
October 11	at Western State (CO)*	Gunnison, CO	W 27–24		[5]
October 25	Texas Western	Memorial Stadium Las Cruces, NM (rivalry)	W 17–16
November 1	at Arizona State	Sun Devil Stadium Tempe, AZ	L 19–23
November 8	McMurry*	Memorial Stadium Las Cruces, NM	W 10–7
November 22	at West Texas State	Buffalo Bowl Canyon, TX	L 32–39
November 28	at Hardin–Simmons	Parramore Stadium Abilene, TX	L 20–26		[6]
*Non-conference game Homecoming