台東天后宮

清治时期

大庄事件平定后，张兆连为感恩妈祖庇佑让当时军队挖井找到水源于光绪十五年（1889年）捐俸建庙，并发动部属及地方士绅共襄盛举。张兆连还在事发地挖的井取名“灵泉井”，立碑石在旁。庙于光绪十七年（1891年）三月落成，落成后光绪皇帝赐颁“灵昭诚佑”匾额一幅。高爵、刘春元、陈炳熙同撰〈埤南天后宫碑记〉。
由当时据守台东的清代官兵出资兴建，因此石碑上赞助官兵有姓元、洋、以、捐等满人音译的姓氏。当时庙址为现在的东禅寺。台湾的妈祖庙有五间官庙，此庙是清朝认证的最后一间，也是东台湾唯一的官庙。
原在埤南宝桑庄之东海滨、光绪七年（1881年）同知袁闻柝所建的昭忠祠，在光绪九年（1893年）遭台风吹倒，暂移祠中神主于此庙之旁，后来重建天后宫时置昭忠祠于右护室。

日治时期

1930年强烈地震引起龟裂，遂有迁建之议。由吴金（吴锦麟）捐出原为菜园的一千六百余坪土地，并由林舍、陈冬路、赖金木、张宜春、林江宁等人，向全台各地信徒筹募经费，历时三年，于1933年落成。当时未立下契约与任何文件，导致后来土地问题。首任主持人张之远因年迈退休，地方士绅公推赖金木主持庙务。
1941年，皇民化运动。一次，警务课长井野边招集台东市绅此妈祖庙开会，主张废除台东所有寺庙，改成神社。首先被问的原住民南医师赞同。第二位身为基督徒的陈姓市绅亦赞同。第三位“台东三赖”之一的赖金木说庙宇是众人所有，应问众人，被井野边责骂。第四位吴金玉则答至少保留天后宫与海山寺，因为是民众的信仰中心，而且战争方殷，为安定人心，废庙不宜。于是，两寺庙皆得以保存。

供奉神祇

主神妈祖分灵的根源，一说是福建湄洲岛。另一说则依《台南大天后宫志》为光绪十五年张兆连对大天后宫献“灵助平蛮”匾时，分灵至台东兴建天后宫，以谢妈祖涌泉救命之恩。大天后促进为交流，还赠有复制“灵助平蛮”匾给台东天后宫，于2010年11月20日揭幕。
胡传日记、《台东州采访册》史料中，胡传将天后宫写成天妃宫，每逢朔望会至此庙、观音祠、土地祠、与昭忠祠参拜。昭忠祠正中央为开山抚番殉难军民的神位，左祀文将军为袁闻柝，右祀武将军为张兆连。
2009年，为“扩展年轻人市场”增加收入，庙内开始供奉月下老人。当时庙方将一本学生作业簿，切割成适合大小，卷塞入月老左手充当姻缘簿，露出“先总统蒋公遗”及半个“训”字正好露在外面。直到香客反应为何月下老人是拿蒋公遗训？庙方才换成红色姻缘簿。 
还有供奉注生娘娘、文昌帝君、观世音菩萨、福德正神、城隍爷等。

清醮祭典

自1953年掌理庙务的林锦泉，于1962年11月举行平安醮，为每逢虎年就举办清醮祭典。
自1962年开始，每隔十二年建醮。建醮期间，台东市民强迫吃素七天，禁屠猪鸡鸭、市场禁止贩售鱼肉、渔船禁止出港，商店肉类罐头也不能上架。警方配合管制，在台东主要对外路口如南回公路、南横公路、台11线、台9线设置拦检哨，禁止外县市肉类进入台东。由邻里长负责家家户户收丁口钱，男的叫“丁”，女的叫“口”，男的钱收的比女的多。后来因男女平等，两性钱都收一样。
入醮时由火醮打头阵，在此庙前起鼓以迎接火神，该刻庙内全面禁火，直到下午5时才送火神回驾。
1986年建醮，时任台北市长的许水德赠送“与天同功”，及时任高雄市长苏南成致赠“后来其苏”桧木匾额，后来在2010年庙方整修时拆下被偷去，出现在拍卖网站，各开价四万元。庙方与业者协调后，业者答应无偿归还。
随着宗教多元化、经济型态改变，建醮收丁口钱、吃素都出现反对声音。2010年，庙方林有德表示收丁口钱不如以往盛况，还有李姓邻长更直言收钱好像被当作诈骗集团和乞丐。