Полк составился в 1863 году из 4-го кадрового и резервных 5-го и 6-го батальонов Белостокского пехотного полка как Белостокский резервный полк, каждый из этих батальонов до 1884 года имел собственную историю, но общее старшинство и знаки отличия. Примечательно, что 5, 6, 7-й и 8-й батальоны полка (в 1863 составившие 126-й Рыльский полк) в продолжение Крымской кампании действовали в Северном Причерноморье, отдельно от первых четырёх батальонов полка, действовавших на Кавказе, поэтому и дарованные знаки отличия за Крымскую кампанию у батальонов 126-го и 50-го полков были совершенно различны, хотя им в 1884 году и присвоена общая история до 1863 года.
С 13 августа 1863 года — Рыльский пехотный полк; 25 марта 1864 года полк получил № 126. В 1879 году сформирован 4-й батальон полка. 18 марта 1884 года всем батальонам полка присвоено старшинство от даты формирования Белостокского пехотного полка, как части, сформированной из его половины, тогда же переписана и история части, ставшей таким образом до 1863 года копией истории Белостокского пехотного полка, одновременно с этим уничтожалась история и изменялись знаки отличия батальонов, входивших в состав полка. В 1907 году полку пожаловано юбилейное Георгиевское знамя с надписью «За Севастополь в 1854 и 1855 годах» с юбилейной Александровской лентой и надписью «1807—1907».
Этот сформирован 30 апреля 1802 года в Закавказье как 3-й батальон Суздальского мушкетерского полка, старшинство ему установлено с 1707 года, как сформированному в этом году из чинов 1-го и 2-го батальонов Суздальского полка. При сформировании батальону выдано два простых знамени, из числа пожалованных Мушкетерскому Генерал-Майора Глазова полку 21 января 1799. 21 августа 1814 года в батальоне оставлено 1 знамя. В 1819 году батальон в кадровом составе со своим знаменем вместе с полком убыл с Кавказа. При этом Суздальский полк приказом Ермолова переименован в Тенгинский (впрочем на старшинство батальонов, сохранивших знамёна это не распространялось). В 1819—1825 годах батальон носил именование батальона Тенгинского пехотного полка, это переименование императором Александром I было 11 мая 1825 отменено и полк стал снова называться Суздальским. 7 октября 1822 года батальону пожаловано новое простое знамя без надписи. 9 мая 1830 года назван 3-м резервным батальоном Суздальского пехотного полка.