104-й полк в составе 76-й Псковской гвардейской дивизии ВДВ был сформирован 24 сентября 1948 года. В 1976 году полк был награжден Красным знаменем за успехи в боевой подготовке. С 1979 по 1989 год его личный и офицерский состав выполнял боевые операции в Афганистане. В феврале 1978 года награжден орденом Красного Знамени за успехи в освоении нового вооружения.
С 1994 по 1995 год полк находился в числе подразделений 76-й дивизии, участвовавшей в боевых действиях в Чечне. Позже участвовал в антитеррористических миссиях на Северном Кавказе.
Полк стал широко известен после боя у высоты 776 во время второй чеченской войны. В ходе сражения под Аргуном 29 февраля — 1 марта 2000 года 6-я рота 2-го батальона 104-го гвардейского парашютно-десантного полка вступила в бой с отрядом из 2,5 тыс. боевиков (данные федеральных сил), которым командовал арабский наемник Хаттаб. Из 90 десантников тогда погибли 84 десантника.
В 2000 году указом президента РФ за мужество и отвагу, проявленные при ликвидации незаконных вооруженных формирований, 22 десантникам было присвоено звание Героя РФ (из них 21 — посмертно), 68 солдат и офицеров 6-й роты были награждены орденом Мужества (63 из них — посмертно).
С начала 2003 года полк был частично переведен на контрактную основу. В 2017 году полк стал одной из первых воинских частей вооруженных сил РФ, удостоенных звания ударной.