The Red Seal system appears from at least 1592, under Toyotomi Hideyoshi, date of the first known mention of the system in a document. The first actually preserved Shuinjō (Red Seal Permit) is dated to 1604, under Tokugawa Ieyasu, first ruler of Tokugawa Japan. Tokugawa issued red-sealed permits to his favourite feudal lords and principal merchants who were interested in foreign trade. By doing so, he was able to control Japanese traders and reduce Japanese piracy in the South Sea. His seal also guaranteed the protection of the ships, since he vowed to pursue any pirate or nation who would violate it.

Besides Japanese traders, 12 European and 11 Chinese residents, including William Adams and Jan Joosten, are known to have received permits. At one point after 1621, Jan Joosten is recorded to have possessed 10 Red Seal Ships for commerce.

Portuguese, Spanish, Dutch, English ships and Asian rulers basically protected Japanese red seal ships, since they had diplomatic relations with the Japanese shōgun. Only Ming China had nothing to do with this practice, because the Empire officially prohibited Japanese ships from entering Chinese ports. (But Ming officials were not able to stop Chinese smugglers from setting sail to Japan.)

In 1635, the Tokugawa Shogunate officially prohibited their citizens from overseas travel (similar to the much later Gentlemen's Agreement of 1907), thus ending the period of red-seal trade. This action caused the Dutch East India Company to become the sole officially sanctioned party for European trades, with Batavia as its Asian headquarters.