"When he left" means the "leaving" was completed, so it matches the perfective aspect well:
"Když odjel, byla smutná".
When using the imperfective (když odjížděl), she was sad during the process of him leaving, but perhaps not after.
There is no preposition here. What do you mean by that?