This work presents a novel scheme for tracking of motion and deformation of interventional tools such as guide-wires and catheters in fluoroscopic X-ray sequences. Being able to track and thus to estimate the correct positions of these tools is crucial in order to offer guidance enhancement during interventions. The task of estimating the apparent motion is particularly challenging due to the low signal-to-noise ratio (SNR) of fluoroscopic images and due to combined motion components originating from patient breathing and tool interactions performed by the physician. The presented approach is based on modeling interventional tools with B-splines whose optimal configuration of control points is determined through efficient discrete optimization. Each control point corresponds to a discrete random variable in a Markov random field (MRF) formulation where a set of labels represents the deformation space. In this context, the optimal curve corresponds to the maximum a posteriori (MAP) estimate of the MRF energy. The main motivation for employing a discrete approach is the possibility to incorporate a multi-directional search space which is robust to local minima. This is of particular interest for curve tracking under large deformation. This work analyzes feasibility of employing efficient first-order MRFs for tracking. In particular it shows how to achieve a good compromise between energy approximations and computational efficiency. Experimental results suggest to define both the external and internal energy in terms of pairwise potential functions. The method was successfully applied to the tracking of guide-wires in fluoroscopic X-ray sequences of several hundred frames which requires extremely robust techniques. Comparisons with state-of-the-art guide-wire tracking algorithms confirm the effectiveness of the proposed method.