Although Zambezia was a part of the Portuguese East Africa Colony, the Portuguese government-issued separate postage stamps for it starting in 1894, with the standard design depicting King Charles, and likewise in 1898. A provisional issue came in 1902 to reflect changed rates, then after the revolution of 1910 there were several issues overprinted "REPUBLICA". The postal districts of Quelimane and Tete were created from parts of Zambezia in about 1913, and then stamps of Mozambique replaced stamps of Zambezia around 1920.