In 1891, the government of German East Africa contracted with the Schülke & Mayr Company to provide mail service along a route from Dar-Es-Salaam to Muansa and Bukoba on Lake Victoria, via Kilossa-Mpapua-Tabora. In 1892, this set (MiNr. Sa-Se) was produced for use with this service.
Due to difficulties with the service, the contract was not renewed the following year, and the stamps were never issued for use.
In 1939, the Schülke & Mayr set was reprinted (3,000 sets) to commemorate the 50th anniversary of the Schülke & Mayr Company. The reprints (MiNr. SNaa-SNae) were printed in the original colors, but lack the burelage of the originals and feature a different perforation (L10.75 vice the original L11.5).