清日馬關條約簽訂後，日軍於明治28年〈1895年〉5月29日登陸澳底，經過一番波折後，於6月7日進入台北城。隨後一路南下接收，卻遭遇台灣人激烈抵抗。直至11月18日，日軍進入台南後，台灣西部已落入日本統治範圍內。
        但是台灣東部仍有清軍殘部劉德杓據守新開園，日軍討伐隊於翌年5月16日自高雄搭艦，5月22日登陸台東，5月25日聯合卑南、馬蘭聯軍擊敗劉德杓部隊，至此才正式統治台東地區。
        卑南二等郵便電信局何時設置
        根據曹潛著「中華郵政史台灣編」一書，由交通部郵政總局1981年出版。書中第633頁記載，「光緒22年1896年4月20日初設卑南二等郵便電信局」。說明卑南郵便局於明治29年〈1896年〉4月20日設置。
        另外，台灣總督府明治29年〈1896年〉4月公文中，列有24個二等郵便電信局及2支局名單，其中同時列有卑南與台東，卑南排在第13個，台東排在第24個，但是台東用紅筆劃掉。後來在4月20日公文中，台東卻已消失了。
        也就是說，當初規劃設置郵便電信局時，台灣總督府搞不清卑南與台東是同一個地方，發現錯誤後才更正。
        因此台灣總督府4月28日府令第2號，公佈二等郵便電信局名單中，台東地區只有卑南郵便電信局。
        但是日軍於5月22日才登陸卑南，卑南郵便電信局有可能於4月開張營業嗎？
        其實日治初期兵荒馬亂，台灣總督府的若干規劃，部分只是制度上存在，實際上未實施。所以卑南郵便電信局不可能於4月設置，那是何時設置？
        通信部於明治29年（1896年）6月2日任命山縣貞一為卑南郵便電信局長，日期回朔自5月10日開始。但是這時日軍尚未進入卑南地區，因此山縣貞一應為籌備設局事宜，而非開局營業。
        日治時期慣例，郵便局設置當天，郵路就同時開設。恆春郵便電信局長澤田卓爾於6月22日發函通信部長土居通豫，說明恆春卑南間郵路已於6月21日開通。
        因此卑南郵便電信局應為明治29年（1896年）6月21日設置。

        明治29年〈1896年〉9月15日，卑南郵便電信局長山縣貞一發函通信部長土居通豫，指卑南郵便電信局本為有土邊的「埤南」，但是為了簡寫，改為無土邊的「卑南」，實際地名為埤南。但是支廳、撫懇署等機關都用「台東」的名字。而且目前從習慣來說，都用台東兩字。所以卑南郵便電信局希望改名為「台東郵便電信局」，以符合實際狀況。
        通信部長土居通豫於10月1日轉函給台灣總督府，指卑南為當地土人稱呼，目前官方大都使用「台東」作為地名，所以卑南郵便電信局希望改名為「台東郵便電信局」。
        此建議獲台灣總督府同意，當時擬定兩案，分別為10月16日及12月1日改名。但因準備不及，決定於12月1日改名。
        明治29年〈1896年〉12月1日，卑南郵便電信局改稱「台東郵便電信局」。
        1946年5月，中華民國政府在臺北成立「交通部臺灣郵電管理局」，同時直屬郵政總局與電信總局，維持日本郵電合辦舊制度。
1947年，交通部以1896年3月20日為國家郵政開辦日，將每年的3月20日訂為「郵政節」。1949年4月1日，臺灣改行中華民國原有的郵電分辦制度，成立「臺灣郵政管理局」、臺灣電信管理局，分別隸屬於交通部郵政總局與交通部電信總局，所屬各級郵政機構同時改組，台東郵局成郵政總局官方使用轄屬地方郵局名稱。
        2003年1月1日，「交通部郵政總局」進行公司化，名稱改制為「中華郵政股份有限公司」，原「郵政管理局」之業務改由「中華郵政總公司」直接管理的責任中心局取代，台東郵局順勢更易為「中華郵政股份有限公司-台東郵局」。