Название Гостиного двора происходит от слова «гость», т.е. купец, ведущий на Руси оптовую и иностранную торговлю и пользующийся многими привилегиями. Первый гостиный двор возник в Москве в начале XVI в., на так называемом Ильинском крестце – пересечении ул. Ильинка и Рыбного пер.

При Иване Грозном деревянное здание Гостиного двора было заменено каменным. Оно не раз горело в московских пожарах. При Алексее Михайловиче Гостиный двор разделился на Старый и Новый. Затем его разделили на четыре двора: Старый, Новый, Соляной и Рыбный.

Рыбный переулок первоначально в XVII в. назывался Введенским по стоявшей в нем церкви Введения Пресвятой Богородицы. В XVIII в. он стал Магистратским переулком – по находившемуся в нем Главному магистрату. Затем получил название по располагавшемуся здесь в XVIII – нач. XIX вв. Общественному рыбному двору (Старым рыбным рядам). После строительства Старого и Нового гостиных дворов переулок фактически стал проездом между фасадами этих зданий. Новый гостиный двор (д. 3) заложен в 1838–40 гг. на месте снесенных Старых рыбных рядов.

В это время Московское купеческое общество, ввиду нехватки площадей в Старом гостином дворе, заказало строительство дополнительных мест для торговли. На месте Старых рыбных рядов появилось трехэтажное здание с протяженным уличным фасадом, расположенным на довольно высоком цокольном этаже. Здание было построено в эпоху позднего классицизма, однако в нем присутствуют детали, присущие времени расцвета ампира.

Стены высокого цокольного этажа отделаны рустом. Главный фасад расчленен тремя заглубленными ризалитами с ионическими портиками, между которыми расположены барельефы. Торжественный характер постройке придают высокие окна парадного этажа с торжественным обрамлением и завершение центрального объема в виде купола.

В 1890 г. на главном фасаде Нового гостиного двора были пробиты дополнительные окна и двери, а также устроены проездные арки, что в целом существенно нарушило первоначальную классическую симметрию.

В наши дни здание занимают некоторые подразделения Росимущества.