After Northern Zhou itself was overthrown by the Sui dynasty in 581, Gao Mai was made a provincial governor.

He became a friend of the important officials Xue Daoheng (薛道衡) and Cui Zujun (崔祖濬), although he was much younger than they were.

As Gao was friendly with Husi, he was demoted and exiled to being the secretary general of Zhuyuan County (朱鳶, in modern northern Vietnam).

In 617, with almost the entire Sui territory engulfed in agrarian rebellions against Emperor Yang's rule, Xiao Xi, a descendant of the Liang dynasty's imperial line, rose as well, declaring a restoration of Liang, and soon seized the modern Hubei and Hunan region and was seeking to expand.

At that time, Gao had become the legal assistant to Qiu He (丘和) the governor of Jiaozhi Commandery (交趾, modern northern Vietnam).

However, when news came that Emperor Yang had been killed in a coup at Jiangdu (江都, in modern Yangzhou, Jiangsu) led by the general Yuwen Huaji, Qiu submitted to Xiao.

When Emperor Taizong found out about this, he demoted Gao to the post of commandant at An Prefecture (安州, roughly modern Xiaogan, Hubei).

Gao was later made the secretary general of Yi Prefecture (益州, roughly modern Chengdu, Sichuan), and as the titular commandant at Yi Prefecture was Emperor Taizong's young son Li Ke the Prince of Shu, Gao was effectively commandant.

In 631, Gao was recalled to the capital to serve as the minister of civil service affairs, and was created the greater title of Duke of Xu.

Soon, however, with many objections to the system, the strongest of which came from Zhangsun Wuji, Emperor Taizong cancelled the scheme, although Gao's title remained Duke of Shen.

In fall 638, he made Gao Pushe (僕射), a head of the important executive bureau of the government and also a post for a chancellor.

However, Wei pointed out that chancellors were supposed to be responsible for all affairs of state, and Emperor Taizong, realizing that he had erred, was humbled.

Emperor Taizong agreed, but had him continue to serve as a chancellor de facto,[3] and also commissioned him and Wei Zheng to lead a project to compile notable literary works into a 1,200-volume compendium known as the Wensi Boyao (文思博要).

Emperor Taizong instead went up on the city walls to watch Gao's funeral procession in order to mourn.