З введенням у 1867 році в дію залізничної ділянки Балта — Ольвіополь на полях поблизу села Катеринка Кам’яномостівської волості Ананьївського повіту Херсонської губернії була облаштована залізнична станція, що отримала назву Катеринка (рос. Екатериновка). Однак, оскільки в Російській імперії вже існувала станція з такою ж назвою, через 8 років щойно збудовану станцію перейменували в Кам’яний Міст по назві найближчого після Катеринки села.
З появою залізничної станції було покладено початок селищу біля неї. Насамперед тут селилися працівники станції та обслуговчий персонал залізничного полотна. Вони мешкали в бараках та казенних пристанційних будинках. Лише наприкінці ХІХ сторіччя тут почали селитися селяни, чиї земельні наділи знаходились поруч зі станцією. Заселялась переважно північна частина прилеглої до стації площі.
З початком примусової колективізації почалась забудова й південної частини. Навпроти станції розмістилась Кам’яномостівська МТС. Майже одночасно з нею виникла нафтобаза для забезпечення паливно-мастильними матеріалами МТС і колгоспів. Тоді ж побудовано й хлібоприймальний пункт «Заготзерна».
В роки німецько-радянської війни станція та селище біля неї зазнали значних руйнувань: висаджено в повітря залізничний вокзал, розграбовано ремонтні майстерні МТС та електростанцію, підірвано нафтові цистерни, вивезено обладнання хлібоприймального пункту, зруйновано більшість громадських споруд.
Після ліквідації в 1958 році МТС, на її базі був створений механічний завод, що згодом виріс у Кам’яномостівський завод сільськогосподарських машин.
У повоєнні роки селище довкола станції активно розбудовувалось, з’являлись нові вулиці.
До 1963 року селище відносилось до Катеринківської сільської ради. У 1963 році були об’єднані Катеринківська та Полтавська сільські ради й утворена нова Кам’яномостівська сільська рада.
