臺東縣警察局前身係日據時期設於臺南民政支部下之臺東出張所，於民國三十年始定名為臺東廳警務課。民國三十四年抗戰勝利後，臺灣光復重歸祖國懷抱並設行省，臺東廳警務課撤銷改稱臺東縣政府警務科，內設有總務、行政、司法三股，並有臺東、關山、新港三警察所暨六十五個派出所，全體員警三０九人。民國三十六年三月二十九日，根據臺灣省縣市組織規程暨臺灣省各縣市政府組織規程準則第七條第三項之法源，成立臺東縣警察局，並將原有三股改為課。

大陸淪陷，臺灣治安日趨重要，本局陸續設經濟、保安、督察等課室，並將臺東、關山、成功三警察所改為臺東、關山、成功三個分局暨成立東峰山地分局，專司山地治安職責，後又撤銷該分局改在警察局設山地警務室，迨至民國四十一年間，凜於治安需要，臺東分局轄知本溪以南另行成立大武分局，連同臺東、關山、成功共為四分局。

民國五十八年迄七十七間因業務需要，組織修編，增置並裁併部分課室，民國八十七年為應充實基層警力修正編制，增置少年警察隊並成立公共關係室；為確保婦幼安全及提升刑案現場採證品質、技術於九十四年九月分別成立婦幼警察隊、鑑識課，民國一0三年為配合地方制度法規定，將課室單位名稱修改為科，另為健全警察機關法制工作及彰顯維繫警察風紀決心，成立法制科、政風室。