Доходный дом купца Патрикеева был построен на стыке XIX-XX веков. У здания, как у многих других домов, расположенных вокруг старой Базарной площади, было «доходное» назначение: на первом этаже размещались торговые лавки, на втором - гостиничные номера

В 1895 г. купец Василий Григорьевич Патрикеев начал строить первую часть дома, расположенную вдоль современной улицы Худайбердина, чуть позже, когда дело пошло, пристроил вторую часть, обращенную к нынешней улице Комсомольской. Третью, предположительно, для складских целей, закончил к 1905 г.

К сожалению, сегодня о купце мы знаем совсем немного и только из косвенных источников. Например, известно, что Патрикеев закупал товары (сладости и/или парфюмерию) у известного московского предпринимателя Адольфа Сиу, поставщика императорского двора, чью кондитерскую фабрику после революции переименовали в «Большевик».
Сохранились также сведения о том, что во время солдатского бунта, случившегося в Стерлитамаке в 1914 г., купец смог откупиться от погрома несколькими бочонками с водкой, сохранив тем самым свое имущество нетронутым. Само здание тоже многое может рассказать о его хозяине. Это крупнейший, по крайней мере из сохранившихся доходных домов, в Стерлитамаке. Высота этажей здесь достигает 4,5 метров, а оконных проемов - 2,5 м. Общая площадь здания - 2970 кв. м. Кирпичный дом строился с применением мощных деревянных балок и металлических рельсов, что позволило выстроить внутри металлические лестничные марши и пристроить внушительные балконы. Межэтажные перекрытия больших помещений были построены с устройством арок Монье (лучковых сводов - в случае Дома Патрикеева - бетонных, опиравшихся на металлические балки) и поддерживались чугунными колоннами.