Recent archaeological discoveries have been made in the norhtern coastal region near Fuzhou that date to the Neolithic Age. On the island of Pingtan, at a site known as Keqiutou, they have found tools made of stones, shells, bones, jades and ceramics. These include wheel made ceramics. They have also found evidence of spinning wheels for yarn and weaving. These artifacts date to between 7450 and 5590 years ago. Another site known as Tanshishan (昙石山) dates to between 5500 and 4000 years ago and is located in the suburbs of Fuzhou. In the lowerlevels of Tanshishan they found semi-circular buildings. Also in another Fuzhou suburb is the Huangtulun site (黄土崙). This is a bronze age site of around 1325 BC.

During the Waring States period, Fujian was the location of the kingdom of Minyue. The word "Mǐnyuè" was derived by combining "Mǐn" (闽), perhaps an ethnic name and associated with the Chinese word for barbarians (蛮; pinyin: mán), and "Yue", after the State of Yue of the Spring and Autumn Period. It is thought that the royal family of Yuè fled to Fujian after their kingdom was annexed by the State of Chu in 306 BC.

Minyue was a de facto independant kingdom until the emperor of Qin Dynasty, the first unified imperial Chinese state, abolished the status. In the aftermath of the fall of the Qin Dynasty, civil war broke out between two warlords, Xiang Yu and Liu Bang. The Minyue king Wuzhu sent his troops to fight alongside Liu Bang, and his gamble paid off. Liu Bang was victorious, and founded the Han Dynasty in 202 BC. Liu restored Minyue's status as a tributary independent kingdom. Thus Wuzhu was allowed to construct his fortified city in Fuzhou as well as a few locations in the Wuyi Mountains. The remains of these have been excavated in recent years. Wuzhu's kingdom extended beyond the borders of contemporary Fujian into eastern Guangdong, eastern Jiangxi, and southern Zhejiang.

After the death of Wuzhu, Minyue maintained its militant tradition and launched several expeditions against the neighboring kingdoms in Guangdong, Jiangxi, and Zhejiang, mostly in the 2nd century BC, only to be stopped by the Han Dynasty. In 111 BC, the Han emperor eventually decided to get rid of the potential threat by sending in large forces simultaneously from four directions via land and sea. The rulers in Fuzhou surrendered to avoid a futile fight and destruction. Thus the first kingdom in Fujian history came to an abrupt end. The people of northern Fujian still erect temples in memory of their first kings.

The Han Dynasty collapsed at the end of the 2nd century AD, paving the way for the Three Kingdoms era. Sun Quan, the founder of the Kingdom of Wu, spent nearly twenty years subduing the Shan Yue people, a branch of the Yue people living in mountains of Fujian.

The first wave of immigration of the noble class arrived in the province in the early 4th century AD when the Western Jin Dynasty collapsed and the north of China was torn apart by invasions by nomadic peoples, as well as civil war. These immigrants were primarily from eight families from central China: Lin (林), Huang (黄), Chen (陈), Zheng (郑), Zhan (詹), Qiu (邱), Ho (何), and Hu (胡). The first four remain as the common surnames of modern Fujian people.

Isolation from nearby areas due to the rugged terrain, contributed to Fujian's relatively backward economy and level of development. Despite the major population boost from northern China during the "barbarian" invasions, population density in Fujian remained low compared to the rest of China. Only two commanderies and sixteen counties were established by the Western Jin Dynasty. Like other southern provinces, Fujian often served as a destination for exiled prisoners and dissidents.

During the Southern and Northern Dynasties era, the Southern Dynasties reigned south of the Yangtze River, including Fujian.

The Tang Dynasty (618–907) oversaw the next golden age of China. As the Tang Dynasty ended, China was torn apart in the period of the Five Dynasties and Ten Kingdoms. During this time, a second major wave of immigration arrived in the safe haven of Fujian, led by general Wang, who set up an independent Kingdom of Min. This kingdom had its capital in Fuzhou. After the death of the founding king, however, the kingdom suffered from internal strife and was soon swallowed up by Southern Tang.

Quanzhou bloomed into a seaport under the reign of the Min Kingdom. It may have been the largest contemporary seaport in the eastern hemisphere. In the early Ming dynasty, Quanzhou was the staging area and supply depot of Zheng He's naval expeditions. From here Zheng He set out on voyages to India, Arabia, Africa and some say he may even have gone east to America. Further development was severely hampered when the Ming Emperor imposed a ban on sea trade. Despite the lifting of the ban in 1550, the area was later superseded by nearby ports of Guangzhou, Hangzhou, Ningbo and Shanghai. Large scale piracy by Wokou (Japanese pirates) in the area was eventually wiped out by Chinese military and Japanese authority of Toyotomi Hideyoshi.

Late Ming and early Qing Dynasty saw another era of large influxes of refugees and another 20 year sea trade ban under the Kangxi Emperor. The ban was a measure intended to counter the refuge Ming government at Koxinga in Taiwan. Incoming refugees, however, did not translate into a major labor force resulting in their re-migration unto prosperous regions of Guangdong province. In 1689, the Qing dynasty officially incorporated Taiwan into Fujian province. Settlement of Taiwan by Han Chinese followed, and the majority of people in Taiwan are descendants of emigrants from Southern Fujian. After Taiwan was separated into its own province in 1885 and ceded to Japan in 1895, Fujian arrived at its present extent. It was substantially influenced by the Japanese after the Treaty of Shimonoseki of 1895 until the Sino-Japanese War (1937-1945) of WWII.

Owing to the mountainous landscape, Fujian was the most secluded province of eastern China. It lacked  rail and had underdeveloped  roads networks, few of which were paved before the 1950s. The first railway to the province was completed in mid-1950s connecting Xiamen to the rest of the mainland. Despite its secluded location, Fujian has had a strong academic tradition since the Southern Song Dynasty.

Since the late 1970s, the economy of Fujian along the coast has greatly benefited from its geographic and cultural proximity to Taiwan. In 2003, Xiamen ranked number eight GDP per capita among 659 Chinese cities, ahead of Shanghai and Beijing, while Fuzhou ranked no. 21 (number 4 among 30 provincial capitals). The development has been accompanied by a large influx of population from the over-populated areas in the north and west.