Trước đây, phố gồm hai đoạn, nằm ở bên ngoài và bên trong cửa ô Ưu Nghĩa, có cổng xây canh gác ban đêm.
Phố Hàng Trứng: đoạn nối từ phố Trần Quang Khải đến ngã tư phố Nguyễn Hữu Huân hiện nay, nằm bên ngoài cửa ô Ưu Nghĩa, được xây dựng trên nền đất xưa thuộc thôn Thanh Yên, tổng Tả Túc (sau đổi thành tổng Phúc Lâm), huyện Thọ Xương cũ. Đình Thanh Yên hiện còn ở số nhà 14A, ngõ Nguyễn Hữu Huân, thờ hai Tiến sĩ họ Vũ và họ Nguyễn. Phố được gọi tên là Hàng Trứng vì nơi đây xưa kia có nhiều nhà buôn bán trứng. Trứng ở đây được đóng trong các sọt lớn, lót rơm và chở bằng thuyền từ Phát Diệm, tỉnh Ninh Bình lên.
Phố Hàng Mắm: đoạn nối từ ngã tư phố Nguyễn Hữu Huân đến phố Hàng Bạc hiện nay, nằm bên trong cửa ô Ưu Nghĩa, được xây dựng trên nền đất xưa thuộc thôn Mỹ Lộc, tổng Hữu Túc, huyện Thọ Xương cũ. Đình Mỹ Lộc hiện còn ở số nhà 45, phố Nguyễn Hữu Huân, thờ Nguyễn Trung Ngạn. Phố được gọi tên là Hàng Mắm vì nơi đây xưa kia chuyên bán các loại mắm cá và thủy sản khác. Nhiều cửa hàng trên phố bày bán mắm tôm đặc để trong chậu sành; mắm tôm loãng đựng trong vại; nước mắm đựng trong những kiệu lớn cao bằng đầu người, chôn xuống đất, đậy nắp, đong bằng thùng gỗ bán dần và cả cua rang muối... Hàng ở đây chủ yếu là bán buôn đi các tỉnh.
Thời Pháp thuộc, phố được gọi là Hàng Mắm (Rue de la Saumure).