Родился в Москве 15 июля 1934 года. Родители будущего художника были далеки от мира искусства, но тягу сына к творчеству поддерживали. В пятнадцать лет Целков решил посвятить себя живописи, начав обучение в художественной школе. После он поступил в Минский театральный институт, но был отчислен за «формализм», отчисляют Целкова и из ленинградского Института живописи, скульптуры и архитектуры имени И.Е. Репина. Желая продолжать художественное образование, Олег Целков поступает в Ленинградский государственный институт театра, музыки и кино. Там его учителем стал Николай Акимов, влияние которого отчетливо прослеживается в творчестве Целкова.
Получив образование Целков переезжает в Москву, где работает оформителем спектаклей, а в свободное время посвящает творческим поискам. Постепенно, его художественный язык обретает неповторимую форму.