Полк составился в 1863 году из 4-го кадрового и резервных 5-го и 6-го батальонов Замосцкого пехотного полка как Замосцкий резервный полк, каждый из этих батальонов имел собственную историю, старшинство и знаки отличия. К августу 1863 года полк переформирован в трёхбатальонный состав и 13 августа 1863 получил наименование Таганрогский пехотный полк, а 25 марта 1864 наименование полка было дополнено № 136. В 1879 году сформирован 4-й батальон полка. 18 марта 1884 года всем батальонам полка присвоено старшинство от даты формирования Замосцкого пехотного полка, как части, сформированной из его половины, тогда же переписана и история части, ставшей таким образом до 1863 года копией истории Замосцкого пехотного полка, одновременно с этим изменялась история и изменялись знаки отличия батальонов, входивших в состав полка
1-м батальоном полка с 1863 года стал 4-й батальон Замосцкого пехотного полка. Этот батальон был сформирован 9 февраля 1834 года как 4-й действующий батальон Замосцкого егерского полка. Батальону установлено старшинство с 1729 года, как сформированному из чинов 1-го батальона Замосцкого полка, имевшего это старшинство. 11 апреля 1834 года пожаловано простое знамя без надписи. 20 июня 1838 года знамени батальона пожалована юбилейная лента. 19 марта 1850 года пожаловано Георгиевское знамя с надписью «За усмирение Трансильвании в 1849 году». 30 августа 1856 года пожаловано Георгиевское знамя с надписью «За усмирение Трансильвании в 1849 году и за Севастополь в 1854 и 1855 годах» (впоследствии это знамя стало полковым знаменем 136-го Таганрогского полка). 6 апреля 1863 года перечислен в новый Замосцкий резервный полк, составив его 1-й батальон. Приказом от 18 марта 1884 старшинство батальона упразднено и юбилейная лента сдана в арсенал.
Батальон в составе Замосцкого полка принимал участие в Венгерском походе 1849 года и Крымской войне.