When the new team started in 1994, Horsens fS had finished sixth in the 1994–95 1st Division season, which qualified AC Horsens to play for promotion to the 1994–95 Superliga through the 1994 Qualifying League. As AC Horsens only won two of 14 matches, and finished last in the Qualifying League, they missed their opportunity of instant promotion for the Superliga. In the first half of the 1994–95 1st Division season, AC Horsens finished at the bottom of the table after winning only a single game, and did not proceed to the Qualification League. In the second half of the season, AC Horsens managed three victories, but finished dead last and were relegated to the 2nd Division. AC Horsens spent two seasons in the 2nd Division before winning promotion back to the 1st Division. From the 1997–98 1st Division season forward, AC Horsens established itself as a consistent part of the 1st Division, as they finished just below the promotion candidates for five seasons in a row. In July 2001, Horsens hired former Danish internationalKent Nielsen as their new manager. The 2002–03 1st Division season did not go well for Den Gule Fare. After the winterbreak halfway through the season, the club was close to relegation to the 2nd Division, but a good ending of the season secured an 11th place, seven points from the relegation zone. In the next season, ACH started out on amazing form. After 15 matches, AC Horsens were leading the 1st Division with 40 points, but a weak finish to the season saw the club surpassed by Silkeborg IF and Randers FC, who won promotion to the Superliga four points ahead of Horsens. In the 2004–05 1st Division season, Horsens finally succeeded in winning promotion. Though amassing only one point more than in the 2003–04 season, AC Horsens finished in the runner-up spot, trailing winners SønderjyskE by a single point. In their first year in the Superliga, AC Horsens became famous for their strong defence, as they finished in 10th place and avoided relegation. They drew 13 of 33 matches; 8 of them ending 0–0. They conceded just 41 goals in 33 matches, a statistic only bettered by the defences of the top-three finishing teams that season. The Superliga season of 2006–07 saw AC Horsens take an early lead over relegation rivals Vejle Boldklub and Silkeborg IF. In the spring of 2007, a slew of strong performances were followed by a series of disappointing defeats and draws, which again brought AC Horsens dangerously close to relegation. New offensive midfielderHenrik Hansen joined the squad midway through the season and became a key player, whereas striker and Canadian national Ali Gerba finished a half-year loan periodin the summer of 2007 without being offered a contract. Instead, Brazilian Gilberto Macena from the Danish 2nd Division East team Holbæk B&I became the top scorer for AC Horsens, netting twelve times during the season.
