История Музея началась 23 апреля 1968 года, когда был заложен первый камень на месте строительства. В тот же день состоялся торжественный митинг по поводу этого знаменательного события.

Стройка была по-настоящему комсомольской. Многие горожане могут похвастать тем, что принимали участие в строительстве музея. На строительную площадку всесоюзного значения отбирались только лучшие комсомольцы. А первая свая была забита Геннадием Сенкевичем, работником стройуправления № 323, которое и строило музей под руководством прораба И. Е. Тихонова.

Строительство велось на деньги, собранные комсомольскими организациями Советского Союза, полученными за работы, выполненные для народного хозяйства, за собранные металлолом и макулатуру (комсомольские организации школ).

14 августа 1971 года музей был торжественно открыт. Первым директором стала учёный и краевед Г. Трофимова, работу над экспозицией будущего музея она начала ещё в 1969 году, когда стройка была ещё на начальном этапе. Экспозиция была посвящена истории комсомольской организации Псковского края.

Своим обликом музей обязан также руководителю коллектива архитекторов и инженеров Александру Белоконю, В. Брайносу и А. Константинову, скульпторам Андрею и Ирине Васнецовым, художнику Борису Тальбергу. Все эти люди удостоены за свою работу премии Ленинского комсомола. Со строительством музея благоустраивалась площадь и прилегающая к ней часть городского парка. Украшением стал цветной фонтан, созданный К. А. Логиновым - Почётным гражданином города Великие Луки.

В 1992 году музей имени Матросова фактически перестал существовать: все предметы из него были переданы в фонд Великолукского краеведческого музея, музей перестал быть именным. Но с 2007 года он получил статус Центра патриотических инициатив и вернул себе имя Александра Матросова. Теперь Центр продолжает традиции музея боевой комсомольской славы.