Marinobacter psychrophilus strain 20041(T) was isolated from sea-ice of the Canadian Basin. Here we report the complete sequence of the 3.9-Mb genome of this strain. The complete genome sequence will facilitate the study of the physiology and evolution of Marinobacter species.