The paper presents an innovative, chemically modified (methylcyanated) asphaltene-based adsorbent that can be an interesting low-cost alternative for traditional adsorbents. Adsorption properties of adsorbents were examined by inverse gas chromatography technique, adsorption isotherms, and breakthrough curves. A significant increase in retention volume for pyridine, 2-pentanone, nitropropane, toluene, and 1-butanol was observed. Rohrschneider–McReynolds constants revealed an increase in strength of interactions as a result of the modification, especially in strong proton–acceptor interaction (by a factor of 4.6). The surface-free energy of asphaltene adsorbents increased from 136.71 to 169.95 mJ m−2 after modification. It is similar to the surface-free energy of silica or alumina. Moreover, modified adsorbent shows very high adsorption potential for pyridine. Adsorption isotherms revealed that monolayer adsorption capacity for pyridine increased 1.5 times after modification. Breakthrough curves of pyridine indicate that chemical modification increased the adsorption capacity, removal efficiency, and throughput. Scale-up calculations revealed that adsorption column packed with modified asphaltene adsorbent would be almost two times smaller compared to a column packed with unmodified one.