Invar alloys with both high strength and low thermal expansion are urgently needed in fields such as overhead power transmission, aero-molds, and so on. In this paper, Cr was introduced as a cost-efficient alloying element into the Fe-36Ni binary invar alloy to increase its mechanical strength. Our results confirmed that fine Cr7C3 precipitants, together with some Fe3C, in the invar alloy aged at 425 °C could be obtained with a short aging time. Those precipitants then grew and aggregated at grain or sub-grain boundaries with an increase in aging time. Simultaneously, mechanical strength and coefficient of thermal expansion (CTE) parabolically varied with the increase in aging time. The sample aged at 425 °C for 7 h presented a maximum strength of 644.4 MPa, together with a minimum coefficient of thermal expansion of 3.30 × 10−6 K−1 in the temperature range of 20–100 °C. This optimized result should be primarily attributed to the precipitation of the nanoscaled Cr7C3.