Происхождение названия по Введенскому Богородицкому монастырю, также называвшемуся Новинским (основан в 1410, упразднён в 1764). Название Новинского монастыря производится от новин — холстов, изготавливавшихся монахинями, и от имени пророка Иисуса Навина. Монастырь располагался за Земляным Валом, к северу от современного Нового Арбата; его владения захватывали современную Конюшковскую улицу и пруды в нижнем течении Пресни. Внутри Земляного Вала в XVII веке находилось село Кудрино и слободы «трубников» (печников) и «кречетников» (специалистов по соколиной охоте).
    В XVIII веке земли слобод перешли в руки землевладельцев-дворян, а монастырские земли за Земляным Валом — в руки чиновников и купцов. Во время пожара 1812 года почти все дома выгорели. Сам вал постепенно пришёл в негодность и был срыт в 1820-е гг.
    Тогда же широкая улица стала местом народных гуляний с балаганами, каруселями («самокатами»), зверинцами, а в 1841 здесь была устроена настоящая увеселительная железная дорога с паровой тягой. Гуляние открывалось на Пасху; первые три дня отводились простонародию, а с четвёртого дня его посещала и «приличная» публика. При этом в течение XIX века бульвар оставался аристократическим районом — здесь жили князья Оболенские, Гагарины, известный адвокат Ф. Н. Плевако, композитор П. И. Чайковский, а в начале XX века целый квартал приобрёл Ф. И. Шаляпин.
    Зелёный бульвар на Новинском гулянии был устроен только в 1860-е гг; в торце бульвара, выходящем на Кудринскую площадь, стояло гостиничное здание, снесённое (как и сам бульвар) в 1937. В связи с посадкой деревьев народное гуляние было в 1862 перенесено в самый центр города, на Красную площадь и Болотную площадь, а также на Девичье Поле. Гуляния на Красной площади просуществовало до 1914.