The football club were originally known as Henan Provincial team and was founded in 1958 by the local government sports body to take part in the 1959 Chinese National Games before joining the gradually expanding Chinese football league system. The team often spent much of its time in the second tier except for a short period during the late 1970s when the league was expanded to accommodate more teams. When the Chinese football league system grew to accommodate a third tier Henan found themselves in it when they were relegated from the second tier in the 1981 league season, however they were able to quickly return to the second tier when they came top of the table to win promotion in the 1982 league season. It wasn't long until they won promotion to the top tier once more in the 1985 league season where they would remain until the 1988 league season when they were relegated at the end of the season.
By the 1994 league season the entire Chinese football league system had become professional and Henan would quickly follow when they became professional on August 27, 1994 and would rename themselves Henan Jianye. Henan's transition toward professionalism was differcult and they were once more relegated at the end of the 1994 league season to the third tier. Once again they would have to win promotion from the third tier when they came runners-up in the table at the 1995 league season. For several season they were a second tier club fighting against relegation until they won promotion to the Chinese Super League at the end of the 2006 league season. In their debut season in the top tier playing professional football Henan brought in Pei Encai to add experience to their management and to help them avoid relegation, which he achieved when they finished the season in 12th position, narrowly avoiding relegation after defeating Changchun Yatai 3:2. While he helped them avoid relegation Henan demanded results in the 2008 league season and this saw them go through several managers before they settled with Tang Yaodong to help them avoid relegation once more. His appointment was to prove extremely successful and throughout the 2009 league season he would lead them to a third place finish, which is the highest league position they have ever achieved.