Officially founded at the end of the 2003 season, the move to create a professional club in Incheon had come about in part by the construction of the Incheon Munhak Stadium for the 2002 FIFA World Cup tournament. Incheon city mayor Ahn Sang-soo began the process of creating the club in earnest in June 2003 with the official founding of Incheon FC, and German Werner Lorant was appointed as manager of the team in September of that year, with Chang Woe-Ryong and Kim Si-Seok added to the coaching staff.
A public share issue was launched and ran from October to November 2003, and in December the name Incheon United was adopted. Sponsorship contracts worth a total of $4m were signed with Daewoo and Daeduk Construction, and a deal was struck with Puma to be the inaugural kit suppliers to the new club.
Lorant and his coaching staff recruited several high-profile players in a bid to make an impact on the league in the club's debut season in 2004. Goalkeeper Shim Bum-chul was recruited along with talented youngsters Choi Tae-Uk, Kim Chi-Woo and popular Japanese playmaker Masakiyo Maezono. The most high profile of the imports was Turkish international defender Alpay Özalan, recruited from English Premier League side Aston Villa.
Despite that promising start to the year, Incheon recorded just one more victory in the first stage of the season and finished bottom of the table on just nine points. The club's fortunes improved slightly during the summer Hauzen Cup tournament, winning three times and finishing eighth out of the thirteen sides involved. Manager Lorant stepped down as manager at the end of August, and he was replaced in the hotseat by his assistant Chang Woe-Ryong as caretaker manager.
Talented former Busan I'cons player Radivoje Manic was added to the squad during the summer transfer window, and both he and caretaker manager Chang made instant impacts on the side as the club finished fourth overall in the second stage of the league season, remaining in the race to claim victory in the stage until the final day.
Chang was confirmed as permanent Incheon manager in January 2005 as the club prepared to embark on what was to become a memorable season. The team finished runners-up in the first stage of the league season and, after coming in eighth for the second consecutive season in the Hauzen Cup, finished joint third in the second stage of the K-League and qualified for the post-season championship playoffs by virtue of having the best overall record. Incheon were to face first stage winners Busan I'Park in the semi-final, and they easily defeated the southern side by a 2–0 scoreline to set up a championship final against Ulsan Hyundai Horang-i. In the first leg of the final at the Munhak stadium, goalkeeper Kim Lee-Sub endured a torrid ninety minutes as Ulsan hit the back of the net five times in a stunning display of football, with Dženan Radončić netting a late consolation goal for the home side. Sung Kyung-Mo replaced Kim in the Incheon goal for the second leg, and though United claimed a 2–1 victory they lost out on the title 6–3 on aggregate, but finished their second season in existence as K-League runners-up.
Incheon United also finished the 2005 season with the highest total and average home attendance, with 316,591 spectators in total coming through the gates, an average of 24,353.
The 2006 season was something of a disappointment compared with the highs of 2005. Tenth overall in the first stage of the K-League and sixth in the second, the team finished bottom of the fourteen-team Hauzen Cup table, but reached the semi-finals of the Korean FA Cup before being eliminated on penalties by eventual winners Chunnam Dragons.
Despite a relative lack of success on the field for the top team, the club continued to strengthen its set-up at reserve and youth level. The reserve team claimed victory in the K-League reserve league championship, and the U12 side won the 2006 Youth Football Championship.
Manager Chang departed for England at the start of the year to begin a year of study, so assistant manager Park Lee-Chun stepped up as caretaker manager for the 2007 season. The club struggled home in 9th place in the regular K-League season, but reached the semi-finals of the FA Cup for the second consecutive season before again losing out to eventual winners Chunnam. There was also an earlier semi-final defeat in the revamped Hauzen Cup competition, where Incheon lost 4–3 on penalties to FC Seoul after a goalless draw in normal time.