This paper presents an open contour tracking method that employs an arc-emission Hidden Markov Model (HMM). The algorithm encodes the shape information of the structure in a spatially deformable trellis model that is iteratively modified to account for observations in subsequent frames. As the open contour is determined on the trellis of an HMM, a dynamic programming procedure reduces the computational complexity to linear in the length of the structure (or contour). The method was developed for tracking general curvilinear structures, and tested on subcellular image sequences, where microtubules grow, shrink and undergo lateral motion from frame to frame. Microtubule length changes are modeled by the addition of appropriate transient and absorbing states to the HMM. Our results provide experimental evidence for the proposed algorithm's capability to track non-rigid curvilinear objects in challenging environments in terms of noise and clutter.