Most powstał z inicjatywy Towarzystwa Rosyjskich Kolei Żelaznych. W pierwszych planach miał być mostem kolejowym łączącym Dworzec Petersburski (obecnie Wileński) z Dworcem Wiedeńskim. Zaniechano jednak prowadzenia kolei przez centrum Warszawy i most ten ukończono wyłącznie jako drogowy (z torami dla tramwajów konnych). Most kolejowy zbudowano kilka lat później, na północ od mostu Kierbedzia, przy warszawskiej Cytadeli (most przy Cytadeli).

Mimo iż Most Kierbedzia był pierwszym stałym mostem od czasów Zygmunta Augusta, a budowę mostu stałego uchwalił jeszcze Sejm Czteroletni, ówczesna prasa nie wspomina o budowie i postępach prac. Most kończono w 1864, tzn. w tym samym roku, w którym upadło powstanie styczniowe. Głównym projektantem był Stanisław Kierbedź – Polak z wysokim rosyjskim stopniem generalskim.

Ogólny koszt budowy przeprawy wyniósł ok. 2,7 mln rubli. Prace zostały wykonane przez francuskie firmy „Goüin et C-ie Batignolles” i „Schneider Creuzot”, której przedstawicielem był francuski inżynier Gottard oraz polski inżynier i wynalazca Stanisław Janicki.

Otwarcie Mostu Kierbedzia nastąpiło 22 listopada 1864.

W czasie zaborów most nosił oficjalną nazwę mostu Aleksandryjskiego (od imienia cara Aleksandra II). Potocznie nazywany był jednak mostem Kierbedzia (od nazwiska projektanta i budowniczego). Z placu Zamkowego prowadziła doń ulica Nowy Zjazd, schodząca z placu Zamkowego wiaduktem Pancera, a później nasypem ziemnym. Po odzyskaniu przez Polskę niepodległości nazwa Most Kierbedzia stała się nazwą oficjalną.

5 sierpnia 1915 około 6 rano wycofujące się z Warszawy wojska rosyjskie wysadziły dwa środkowe przęsła, nie uszkadzając filarów. Most został odbudowany w 1916, jednak nowe kratownice różniły się od zaprojektowanych przez Kierbedzia (ich górny pas miał kształt paraboli).