A method with video segmentation may include: acquiring, over time, a video sequence including a plurality of image frames, the plurality of image frames including a second image frame corresponding to a time t of the video sequence and a first image frame corresponding to a time t−1 before the time t; extracting a second feature vector from the second image frame; generating second hidden state information corresponding to the second image frame, based on first hidden state information corresponding to the first image frame and second fusion information in which the second feature vector is fused with information related to the second image frame stored in a memory; generating a second segmentation mask corresponding to the second image frame, based on an output vector corresponding to the second hidden state information; and outputting the second segmentation mask.