As an ideal material for flexible sensors, electrically conductive hydrogels (ECHs) has been faced with water loss and easy freezing, which affects the conductive and tensile properties. Polyacrylamide/sodium alginate/LiCl (PAM/SA/LiCl) hydrogel was constructed to enhance the anti-freezing property without deficiencies of tensile and electrical performance. A semi-interpenetrating network (semi-IPN) was formed by PAM and SA through hydrogen bonding, which performed excellent mechanical property (fracture strain 2100%, fracture stress 110 KPa). LiCl contributed to the high ionic conductivity (up to 21.7 S/m) and sensitivity (Gauge Factor (GF) = 17.45). Double hydrogen bonding of SA and PAM, hydration of LiCl and ion interaction between SA and lithium ion improved the anti-freezing performance and mechanical property of the hydrogel together. The proportion of non-freezing water in system was proved to be significantly increased. The comprehensive properties of the hydrogels were evaluated and PAM/SA/3M LiCl hydrogel kept conductive without obvious loss of stretchability at −30 °C. The PAM/SA/LiCl hydrogel integrates remarkable toughness, conductivity, sensitivity and anti-freezing property, which is a suitable choice in smart wearable devices, soft robots and medical monitoring.