Born in Northumberland, Coldstream moved to London as a small child with his family. He studied at the Slade School of Fine Arts in London from 1926 to 1929, and in his final year, exhibited with both the New English Art Club and the London Group, to which he was elected a member in 1934.
Troubled by the social conditions endured by others during the Depression and by his own problems capturing this adequately in his art, Coldstream gave up painting in 1934 in order to make documentary films. He resumed painting in 1937, with the financial support of Kenneth Clark, and later that year helped establish a school of drawing and painting in Fitzroy Street, London, along with Claude Rogers and Victor Pasmore. After moving to new premises, this became popularly known as the Euston Road School, which as a term was soon also applied to the socially committed realist style in which they painted.

Coldstream continued teaching at the Euston Road School until the outbreak of World War II, when he joined the Royal Engineers. He was appointed an Official War Artist in 1943, working first in Egypt and then in Italy. After World War II he began teaching at the Camberwell School of Arts and Crafts in London and, in 1949, was appointed Slade Professor at University College, London (a post that he held until 1975). His influence as a teacher at the Slade School of Fine Arts was immense, not just on those who worked in a similar style to his own, such as Euan Uglow, but on painters working in other styles even after his retirement.

The austerity and discipline of Coldstream's early work, with its social and political concerns, remained essential to his later practice as a painter and in particular to his dedication to visible yet disciplined marks. His method was slow and painstaking, and he held only four one-man exhibitions in his life, the last in 1984. He remained convinced of the importance of painting as accurately as possible from direct observation.