Results of a two-particle correlation analysis of high-$p_t$ charged particles in Pb-Au collisions at 158$A$ GeV/$c$ are presented. The data have been recorded by the CERES experiment at the CERN-SPS. The correlations are studied as function of transverse momentum, particle charge and collision centrality. We observe a jet-like structure in the vicinity of a high-$p_t$ trigger particle and a broad back-to-back distribution. The yields of associated particles per trigger show a strong dependence on the trigger/associate charge combination. A comparison to PYTHIA confirms the jet-like pattern at the near-side but suggests a strong modification at the away-side, implying significant energy transfer of the hard-scattered parton to the medium.