We present interstellar scintillation velocity measurements for four millisecond pulsars obtained from long-term monitoring observations with the Arecibo radio telescope at 430 MHz. We also derive explicit expressions that relate the measured scintillation velocity to the effective transverse velocity responsible for the motion of the diffraction pattern for both binary and solitary pulsars. For B1257+12, B1534+12, J1640+2224, and J1713+0747 we derive velocity estimates of 197, 192, 38, and 82 km/s, respectively. These values are in good agreement with proper motion measurements for the four pulsars. For PSR B1534+12, we use the ISS velocity dependence on orbital phase to determine the longitude of the ascending node (Omega) of the pulsar's orbit and to derive an estimate of the effective scattering screen location. The two possible values of Omega are 70+/-20 and 290+/-20 degrees and the approximate screen location is 630+/-200 pc with the assumed pulsar distance of 1.1 kpc.