Музей расположен в историческом центре Вологды в двухэтажном каменном здании, которое ранее принадлежало Госбанку и является объектом культурного наследия федерального значения середины XIX века. Это здание связано с именами двух известных вологжан прошлого. Первым владельцем был Александр Васильевич Сорокин, выходец из удельных крестьян села Турундаева Вологодского уезда, который сколотил значительное состояние в купечестве. Он неоднократно избирался гласным Вологодской Городской Думы и дважды занимал пост городского головы Вологды. В 1859 году Сорокин продал дом подполковнику Николаю Петровичу Брянчанинову, представителю известного в Вологодской губернии дворянского рода. Общая площадь здания составляет 1500 м². В 2008 году на реставрацию из областного бюджета было выделено 56 миллионов рублей.

В 2008 году идея губернатора Вологодской области Вячеслава Позгалёва о создании в Вологде музея кружева получила поддержку министерства культуры РФ, правительства РФ и президента России Дмитрия Медведева. Финансирование осуществлялось в рамках ведомственной целевой программы «Наследие Вологодчины», и на эти цели из областного бюджета было выделено около 270 миллионов рублей. В 2010 году из федерального бюджета дополнительно выделили 50 миллионов рублей в рамках программы «Культура России» для завершения создания экспозиции. Художественное проектирование музея выполнил вологодский художник-дизайнер Сергей Михайлович Иевлев, член Союза художников России.

Музей кружева открылся 3 ноября 2010 года. На торжественном открытии присутствовали представители генеральных консульств Польши, Германии, Франции, Бельгии, Австрии, руководство министерства культуры РФ, губернатор Вологодской области Вячеслав Позгалев, глава города Вологды Евгений Шулепов, а также депутаты Законодательного собрания Вологодской области и Вологодской городской думы. С 5 ноября музей открыт для посещения и экскурсий.