We present Halpha + [N II] images, optical long-slit spectroscopy, and high-resolution CO interferometry of the strongly disturbed Virgo Cluster spiral galaxy NGC 4438, which has recently undergone a high-velocity (900 km s-1) collision with the nearby S0 galaxy NGC 4435. CO is detected from an unperturbed circumnuclear disk 1.5 kpc in radial extent. Optical line images reveal several remarkable ionized gas filaments which originate from the disk plane approximately 1.5-3.5 kpc from the nucleus and extend out of the disk for approximately 5-10 kpc toward the west and southwest. Spectroscopy shows these filaments to be shock-excited and kinematically distinct from the ionized and molecular gas in the circumnuclear disk. The filaments connect this gas-rich nuclear disk to a second gas-rich region with strong [N II], X-ray, radio continuum, CO and H I emission located 5 kpc to the NW. The gas in the filaments has line-of-sight velocities which are within approximately 200 km s-1 of the galaxy's systemic velocity; thus, it has insufficient energy to escape the galaxy and may be infalling. We also present optical spectroscopy of the colliding partner, NGC 4435, which reveals line emission from a rapidly rotating core 4'' (300 pc) in extent. The kinematics and morphology of this circumnuclear ionized gas are consistent with a rotating disk coplanar with the stars, suggesting that gas existed in NGC 4435 prior to the collision. Halpha absorption reveals a population of A-type stars, indicating star formation within the last 10(9) yr. We propose that the origin for most features of the disturbed ISM in the system is a high-velocity ISM-ISM collision between the massive gas-rich galaxy NGC 4438 and the less massive, less gas-rich galaxy NGC 4435. In such a collision, some gas from the larger, gas-rich galaxy will be strongly heated and perturbed but not given a large enough impulse to escape and will ultimately fall back into the galaxy. The disturbed ISM in NGC 4438 is similar in many ways to the gaseous nebulae around E/cD galaxies with inferred cooling flows. We argue that the optical filaments arise where hot gas comes into contact with colder gas as both resettle into NGC 4438 in the aftermath of the collision, creating layers of shocked gas at the boundaries. We emphasize that close, high-velocity collisions between large galaxies in clusters can partially destroy stellar and gaseous disks and may also drive gas toward the center, thereby transforming spirals into earlier type spirals or lenticulars.