Il bastione conserva evidenti tracce degli interventi di fortificazione che si sono succeduti nel corso dei secoli. Fu edificato al tempo di Niccolò V Parentucelli (1447-1455), cui si deve la costruzione di torrioni cilindrici in corrispondenza di tre dei quattro vertici del basamento romano del Mausoleo.
Al tempo di Alessandro VI Borgia (1492-1503), i maestri lombardi Giacomino e Antonio di Giovanni inglobarono il torrione, posto in corrispondenza di questo angolo, entro un muro poligonale a sette lati contenente all’interno cannoniere e condotti di aerazione. La sua cortina esterna raggiungeva in altezza il Passetto di Borgo, al quale tuttora si congiunge.
A Pio IV Medici (1559-1565) si deve l’assetto attuale della struttura: durante il suo pontificato, il livello del Bastione fu elevato fino ad occultare al suo interno la torretta di Niccolò V (eliminata infine nel corso del XVII sec.) e ad essa fu addossata una rampa elicoidale di collegamento alla marcia ronda. Furono aperte, all'interno, 16 celle radiali adibite a cannoniere.
Per volere di Pio IV fu anche edificato, a ridosso del bastione, un edificio a più livelli. Tale costruzione, che doveva in origine ospitare prigioni al pian terreno, fu in seguito utilizzata come caserma, dormitorio e deposito per attrezzi e materiale bellico. L'edificio ospita attualmente una parte degli uffici e la biblioteca del museo.
Al tempo di Urbano VIII Barberini (1622-1644) la struttura del bastione fu nuovamente rafforzata per adattarla staticamente all’uso di pezzi di artiglieria pesante. Nell’ambito di tale intervento furono occultate quasi del tutto le fasi costruttive precedenti. Nei primi decenni del Novecento, sotto la direzione del Generale Borgatti, primo direttore del museo, il bastione San Marco fu oggetto di notevoli lavori di restauro. Risale allo stesso periodo la ricostruzione della Mola del Castello, allestita in una delle celle radiali, dove Borgatti fece sistemare i frammenti ricomposti di tre pietre da mola ritrovati durante i lavori di sterro eseguiti nell’Ambulacro di Bonifacio IX.