Ein erstes Postamt ist in Labuan seit 1864 bekannt.

Als Poststempel wurde ein kreisförmiger Datumsstempel benutzt. Einige Briefe aus Labuan waren mit Briefmarken aus Indien und Hong Kong frankiert, aber wahrscheinlich wurden sie von Reisenden mitgebracht und nicht in Labuan verkauft. Zunächst wurden Postsendungen über Singapur weitergeleitet. Ab 1867 benutzt Labuan offiziell die Briefmarken der Straits Settlements. Die ersten eigenen Briefmarken wurden im Mai 1879 ausgegeben.

Die ersten Briefmarken von Labuan zeigen den Gepflogenheiten der damaligen Zeit entsprechend das Profil Queen Victorias. Ungewöhnlich war eine Beschriftung in arabischen und chinesischen Schriftzeichen neben der Bezeichnung LABUAN POSTAGE. Versorgungsengpässe bei der Nachlieferung führten in den 1880er Jahren zu einer Vielzahl von Aufdrucken. Die Originalmarken waren geprägt, aber die letzten Marken dieser Ausgabe wurden im April 1894 durch Lithographie hergestellt.

Ab Mai 1894 wurden die Ausgaben von Nordborneo in verschiedenen Farben gedruckt, wobei „Labuan“ entweder in die Vignette eingeprägt oder als Aufdruck ausgeführt wurde. Am 24. September 1896, zum 50. Jubiläum der Abtretung Labuans, wurde eine Sonderausgabe hergestellt, bei der die Nordborneoausgabe mit „1846 / JUBILEE / 1896“ überbedruckt wurde. Weitere Aufdrucke sind aus den 1890er Jahren bekannt. 1899 wurden viele Markenwerte mit einem Aufschlag von vier Cents versehen.

Die letzte reine Labuan-Ausgabe mit einer Krone und der Inschrift „LABUAN COLONY“ erschien 1902. Nach der Eingliederung Labuans in die Straits Settlements im Jahr 1906 stellte Labuan die Ausgabe eigener Briefmarken ein. Die Verwendung der bereits gedruckten Briefmarken war für eine Übergangszeit noch erlaubt. Viele der verbliebenen Briefmarken wurden amtlich entwertet und an Sammler abgegeben. Diese Marken sind heute nicht mehr viel wert. Anders verhält es sich mit den originalen Briefmarken von Labuan, die zu erheblichen Preisen gehandelte werden.