По преданию, монастырь основал инок Варлаам, который принес сюда икону святителя Николы Чудотворца из итальянского города Бар. Старец-странник Варлаам, ростовский инок, паломником путешествовал в Грецию, Палестину и Италию, в г. Бар, с целью осуществить заветную мечту — поклониться гробу святителя Николы.
Во время посещения им г. Бара он приложился к мощам святого. После этого иноку во сне явился сам угодник Божий и велел ему купить на торгу его образ, обещая воздать благодать и покровительство иноку. С этим образом он повелел ему идти в Россию и поселиться с иконой там, где ему будет снова указано. Инок так и сделал. Согласно указанием угодника Божия, он пошел на торг и действительно купил образ за три серебреника и немедленно отправился с ним из Бара на свою родину. С великой радостью благополучно под покровом чудотворца старец прибыл в Россию в город Углич на самый праздник перенесения честных мощей святителя 9 мая 1460 года. Тут он остановился на несколько дней, а затем пустился в дорогу в Ростов.
Однако, едва только он отошел от Углича 12 верст до реки Улеймы, как здесь в пустынном, лесистом месте почувствовал сильную усталость, так что не мог дальше продолжать свой путь. Тогда инок Варлаам остановился, поставил образ Николы на сосну между ветвей, а сам, помолившись, лег на землю и уснул. Проснувшись после небольшого сна, он встал и хотел снять икону с дерева, чтобы опять идти дальше, но, лишь только коснулся образа, тотчас ослабели его руки, а образ не двинулся с дерева.
Во второй и в третий раз пытался он взять чудную икону, и все безуспешно. Смутился этим старец и, не зная, что ему делать, в горе лег и заснул. Ночью происходит новое явление святителя Николы старцу, который слышит слова чудотворца:
Остановись здесь с моим образом, хочу иконою моею прославить место сие, и на месте этом будет поставлена обитель моя, благодать Божия и молитвы мои будут здесь.
И действительно, как бы в удостоверение обещания святителя, немедленно начались чудеса от образа его.
Недалеко, тоже на реке Улейме, находилось село Дуброво. Крестьяне его, встретив случайно старца Варлаама, поселившегося при образе, и услышав от него о дивных делах иконы, тотчас же привели к нему многих больных, и они заступничеством чудотворца Николы все исцелились.
Жители окрестных мест построили часовню при самой дороге в Ростов, туда и был перенесен образ.
Весть об этом дошла и до князя Андрея Васильевича Углицкого, который и повелел в 1469 году начать строительство обители и первого деревянного храма во имя Николы Чудотворца. В 1563 году углицкий князь Юрий Васильевич построил здесь деревянную церковь Введения во храм Пресвятой Богородицы, а в 1589 году, при царевиче Димитрии, был построен соборный храм во имя святителя Христова Николы,куда был перенесен чудотворный образ. Обитель была окружена деревянной стеной. Она владела несколькими селами и деревнями.
В 1609 году начались для монастыря страшные испытания. Вместе со всей русской землей Николо-Улейминский монастырь пострадал во время польско-литовской интервенции. Соборный храм был взорван.
Строительство нового Никольского собора на подклете прежнего началось в 1620-е годы, однако освящён собор был лишь 9 мая 1677 года Ростовским митрополитом Ионой Сысоевичем.
Введенская церковь была построена в XVI веке.
В 1707 году боярыня П. А. Нарышкина передала собору частичку мощей Николы Чудотворца, привезённых в Россию царём Петром I.
В 1713—1717 годах была построена надвратная церковь во имя Святой Животворящей Троицы.
В 1930 году монастырь был закрыт. Церковная утварь была вывезена в музеи Углича и Ярославля.
Монастырь использовали под школу, под скотоводческие фермы, хранилище для зерна; использовались храмы и под лагерь заключённых (с 1938 года), и под детский дом (в 1941—1957 годах), и под психоневрологический детский дом-интернат. В 1941 году с башен были сняты кровли, и башни были переоборудованы в укрепления для отражения врага. На северо-запад, северо-восток и юго-восток протянулись противотанковые рвы. Всё это ускорило разрушение монастыря. Юго-восточная башня была наполовину разрушена. В 1950-х годах от грозы сгорел крест на колокольне Никольского собора.
В 1960 году была начата реставрация зданий. Силами Угличского реставрационного участка под научным руководством С. Е. Новикова была укреплена восточная стена и отремонтированы южные башни. Отреставрированы были стены и крыльцо на два схода у Введенского храма. Восстановлены древние наличники с редким «звёздчатым» сандриком. Отремонтировано крыльцо Троицкого храма, перекрыты главы Никольского собора и Введенской церкви, над ними установили позолоченные кресты. Восстановлен крест и на колокольне Никольского собора. В этот период исчез южный придел Никольского собора, исчезли и решётки из его окон, осыпалась роспись.
В 1992 году Свято-Никольский Улейминский монастырь был передан Русской православной старообрядческой церкви (Белокриницкое согласие) и возродился как мужской монастырь. Весомый вклад в реставрацию всего комплекса внесла благотворительница Л.Л. Беломестных.
28 мая 1993 года в день 400-летия гибели царевича Димитрия в Никольском храме монастыря был совершён молебен с водосвятием. Это была первая служба после закрытия монастыря и первая служба староверов в этих стенах.
Из-за малочисленности насельников в 1998 году монастырь был превращён в женский.
На сегодняшний день в обители проживают 12 сестёр.