Родился в г. Париж в семье врача. Русский. Мать - Инна Никандровна Рашевская - врач. По семейным преданиям - прямой потомок украинского гетмана Павла Полуботка

С 1900 года жил в Петербурге.
По другим данным - детство и юность Шеболдаева прошли в Ставрополе. Воспитанник мужской классической гимназии Борис Шеболдаев в 1914 году организовал вместе с такими же, как он "сорванцами", социал-демократическую группу. Та группа развернула активную борьбу против начавшейся войны. Выпустили листовку к солдатам воинских частей, расквартированных в Ставрополе. Юных подпольщиков вскоре арестовали. Юный Шеболдаев отделался ссылкой в Туруханский край – примерно в те же места, где тогда сидел Сталин. В документах полиции Шеболдаев получил кличку "Пампушка" – вероятно, из-за своего "интеллигентского происхождения".

В 1914 вступил в РСДРП, большевик. В 1916 году был мобилизован (заменена ссылка) в Российскую армию - санитар на Кавказском фронте. В 1917 был председателем местного комитета большевиков в Эрзеруме

В 1917 году был заместителем председателя ВРК Кавказской армии. В 1918 году стал членом Бакинского комитета РКП(б) и заместителем наркома по военным делам Бакинского Совнаркома и в дальнейшем был уполномоченным РВС 12-й армии РККА.

В Баку был арестован англичанами, но сумел бежать вместе с А.Микояном.

В 1920 - ответ. секретарь Дагестанского обкома РКП(б) и заместитель председателя ревкома Дагестана.
С декабря 1920 работал в аппарате ЦК РКП(б) в Москве.
в 1923-1924 гг. заведующий отделом ЦК КП(б) Туркесатана.
в 1924-1925 гг. секретарь Царицынского губкома РКП(б). /инициатор переименования города в Сталинград/
в 1925-1928 - заместитель заведующего отделом ЦК ВКП(б).
В 1928-1930 -первый секретарь Нижне-Волжского крайкома ВКП(б).
В 1931-1934 - первый секретарь Северо-Кавказского крайкома ВКП(б).
В 1934-1937- первый секретарь Азово-Черноморского крайкома ВКП(б).

30.12.1936 выехал в командировку в Москву.
2 января 1937 ЦК ВКП(б) принял постановление "Об ошибках секретаря Азово-Черноморского краевого комитета т. Шеболдаева и неудовлетворительном партийном руководстве крайкомом ВКП(б)", в котором Ш. обвинялся в "политической близорукости.. засорил парторганизацию края врагами народа всех мастей... проявил "совершенно нетерпимую политическую близорукость", и в результате на руководящих постах в крае "вели подрывную работу заклятые враги партии, шпионы и вредители – троцкисты".

В 1937 г. - первый секретарь Курского обкома ВКП(б).

в 1930-1937 гг. член ЦК ВКП(б). в 1927-1930 гг. член ЦКК ВКП(б). Член ЦИК СССР. Делегат XV-XVII съездов ВКП(б).

По утверждениям Н.С. Хрущева на XVII съезде ВКП(б) передал С. М. Кирову пожелание "стариков" сместить И. В. Сталина с поста генерального секретаря.

награжден орденом Красного Знамени

Арест и гибель
По утверждению О. Шатуновской, поводом для ареста и последующего расстрела Шеболдаева стала информация, полученная им на допросе В. Каспаровой в Новочеркасской тюрьме в 1936 году. Со слов Шатуновской, "Сталин поручил Шеболдаеву сказать Каспаровой, что если она откажется от того, что говорила в его адрес, то он ее пощадит и сохранит ее жизнь… В ответ на это Каспарова вскочила с тюремной койки и яростно закричала: "Я знаю, что Сталин - провокатор, агент царской охранки! Говорила это и буду говорить до самой смерти, никогда не откажусь от этих слов".

10 июня 1937 года арестован. Постановлением Июньского (1937) пленума ЦК ВКП(б) выведен из состава членов ЦК ВКП(б). Приговорен ВК ВС СССР 30 октября к расстрелу и расстрелян в тот же день. Захоронен на Донском кладбище.

14 марта 1956 реабилитирован и посмертно восстановлен в партии.

Жена - Соколова - пред. Азово-Черноморского крайсовпрофа, была арестована будучи беременной, родила сына и была расстреляна. Якобы, был усыновлен, домработницей Шеболдаевых и вместе с ней выслан в Сибирь.
https://document.wikireading.ru/30520

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