We address semi-supervised video object segmentation, the task ofautomatically generating accurate and consistent pixel masks for objects in avideo sequence, given the first-frame ground truth annotations. Towards thisgoal, we present the PReMVOS algorithm (Proposal-generation, Refinement andMerging for Video Object Segmentation). Our method separates this problem intotwo steps, first generating a set of accurate object segmentation maskproposals for each video frame and then selecting and merging these proposalsinto accurate and temporally consistent pixel-wise object tracks over a videosequence in a way which is designed to specifically tackle the difficultchallenges involved with segmenting multiple objects across a video sequence.Our approach surpasses all previous state-of-the-art results on the DAVIS 2017video object segmentation benchmark with a J & F mean score of 71.6 on thetest-dev dataset, and achieves first place in both the DAVIS 2018 Video ObjectSegmentation Challenge and the YouTube-VOS 1st Large-scale Video ObjectSegmentation Challenge.