Улица возникла после получения Рыбинском статуса города в 1777 году и принятия генерального плана застройки в 1784 году. По плану город Рыбинск приобретал регулярную сетку улиц с прямоугольными кварталами. Главными улицами становились Крестовая и Постоялая (сейчас Стоялая). Крестовая улица шла с юго-востока на северо-запад параллельно Волге. Остальные улицы либо шли параллельно Крестовой, либо пересекались с ней под углом 90 градусов.
Название улицы происходит из-за пересечения со Стоялой улицей. Пересечение двух главных торговых улиц называлось Торговой площадью или Крестом (по старинному перекресток — крестец, крест)[1]. Здесь до начала активной деятельности биржи совершались торговые сделки и находилось место сбора торговых налогов, пошлин — мыты. Отсюда произошло название расположенного на улице Мытного рынка.
К 1917 году длина улицы составляла 2,1 километра и проходила до Коммерческой улицы (сейчас улица Свободы), по которой проходила западная граница города.
В 1918 году улица была переименована в проспект Ленина в честь советского руководителя В. И. Ленина. В советское время улица была продолжена в направлении северо-запада, ее общая длина составила 4,5 километра. В 1994-м году историческому участку от Соборной площади до улицы Свободы вернули историческое название Крестовая, а построенный в советское время западный участок сохранил имя Ленина.
В 2019 году была проведена реконструкция Крестовой улицы[2]. Помимо ремонта асфальтового покрытия проезжей части и мощения тротуаров новой тротуарной плиткой, были установлены новые опоры освещения и троллейбусной сети, стилизованные под исторические столбы; убраны под землю многочисленные провода. Перекресток Крестовой и Стоялой улиц был вымощен брусчаткой. Также был произведен ремонт фасадов зданий в начале улицы и замена вывесок на стилизованные под дореволюционную орфографию.
До 2012 года улица Крестовая на всем ее протяжении была закрыта для движения личного автотранспорта. В 2012 году было проведено расширение улицы от площади Дерунова до универмага «Юбилейный» с установкой светофора на улице Кирова. После этого участок от площади Дерунова до улицы Луначарского был открыт для проезда легкового автотранспорта. После расширения параллельной улицы Волжская Набережная была открыта и остальная часть Крестовой улицы [3].