Automatic video object segmentation and tracking is a challenging problem. In this paper, we introduce a new systematic method for fully automatic object segmentation and tracking using probabilistic fuzzy c-means and Gibbs random fields. The spatial segmentation is based on probabilistic fuzzy c-means clustering and Gibbs sampling. The obtained segmented mask is then refined by taking into account of motion information. Motion vectors are calculated using block matching method based on phase correlation. The motion features and their spatial relationships are used to associate the segmented regions to form video objects. Temporal tracking is achieved by projecting the blocks in current frame to the next frame. The motion-compensated prediction is carried out directly over membership matrix which is used as the initialization of probabilistic fuzzy c-means clustering for the next frame. Experimental results show that the proposed method can automatically extract and track the video object in cluttered background. The major advantages of the proposed method are its ability to deal with deformable objects and being fully automatic