Surface-deposition of destabilised colloidal particles of asphaltenes poses a serious and costly problem during petroleum production. Remediation of asphaltene-fouled well-bore and surface facilities is often undertaken by flowing aromatic solvent to remove deposited films. However, little is known about the properties of deposited asphaltene films during their removal by solvent-rinsing. Here, we carry out quartz crystal microbalance with dissipation monitoring (QCM-D) experiments to investigate surface-deposition of destabilized colloidal particles of asphaltenes and their subsequent removal by solvent-rinsing. It is shown that the properties of deposited films during solvent removal depend on the history of the deposit. Newly formed deposit films are removed immediately without significant change in their mechanical properties during removal. However, deposits that remain on the surface for an extended time in a poor solvent (a low-asphaltene solubility solvent), “aged deposits”, are more difficult to remove and exhibit increased dissipation during the removal period, indicating that they swell and are softer. Liquid-cell atomic force microscopy (AFM) confirms that aged deposits swell when the quality of the solvent is subsequently improved by exchanging for a high-asphaltene solubility solvent. Deposit swelling is accompanied by a change in film morphology, from particulate to continuous. Stubborn deposits of aged asphaltene films, which remain after solvent-rinsing, may be partly removed by flowing dissolved asphaltenes in good solvent. Hence, reinjection of asphaltenes during remediation can aid deposit removal.