Phố Hàng Khoai nguyên là đất thôn Huyền Thiên, tổng Hậu Túc (sau đổi thành tổng Đồng Xuân) huyện Thọ Xương cũ.
Trước đây nơi này tập trung các hàng bán các loại khoai khác nhau nên mới có tên gọi như vậy. Ở giữa phố Hàng Khoai, tại số nhà 54 là chùa Huyền Thiên hay đền Huyền Thiên, là nơi thờ Huyền Thiên Trần Vũ, tức "ông thánh" vốn được thờ ở đền Quán Thánh. Đây là ngôi chùa cổ, thờ cúng Đạo giáo. Trong chùa vẫn còn một tấm bia dựng vào năm Cảnh Trị thứ 6 (năm 1668). Xưa hơn nữa, Trần Nguyên Đán cũng đã từng có một bài thơ đề vịnh quán này:
Bạch nhật thăng thiên dị
Trí quân Nghiêu Thuấn nan
Trần ai lục thập tải
Hồi thủ qúy hoàng quan.
Dịch:
Ban ngày bay lên trời đi
Đi tìm Nghiêu Thuấn khó khăn
Trần tục sáu mươi năm
Thẹn thùng đối mặt khách khăn vàng
Tên phố thời Pháp thuộc là rue des Tubercules (phố các củ).