Королёв родился в рабочем посёлке Тербуны Липецкой области. Был пятым из шести детей в семье. Отец, участник трех войн, работал инженером на предприятии «Сельхозтехника», мать — бухгалтер.
Окончил техникум лесного хозяйства и заочное отделение Саратовского сельхозинститута, а также Ростовскую высшую партийную школу.
В 1973 году был определён лесничим в Долгоруковское лесничество Тербунского лесхоза. Затем занимал ряд низших партийных должностей в Долгоруковском районе Липецкой области: инструктор Долгоруковского райкома КПСС, заместитель председателя — секретарь партбюро колхоза «Путь к коммунизму». Одновременно продолжал заочную учёбу в Саратовском институте. В 1978—1984 годах — председатель колхоза «Память Ильича».
С 1985 года — второй секретарь Долгоруковского райкома КПСС, с 1987 года — первый секретарь Добринского райкома КПСС. Согласно утверждению самого Королева, в 1989 году он был снят с последней должности после своего выступления на одном из демократических митингов в московских «Лужниках». После ухода с поста стал генеральным директором объединения «Липецкводмелиорация» (1989—1990).
В 1990 году был избран депутатом липецкого областного Совета народных депутатов. С 1990 по 1992 год возглавлял аграрную комиссию облсовета. В августе 1991 года вышел из КПСС; до 2003 года не был членом ни одной политической партии. В мае 1992 года был избран председателем липецкого областного Совета депутатов и оставался на этой должности вплоть до избрания главой администрации области в 1998 году.
22 сентября 1993 года малый совет липецкого облсовета принял решение о неконституционности указа № 1400 президента Российской Федерации «О поэтапной конституционной реформе в Российской Федерации» и подтвердил свое решение месяц спустя. Вплоть до 26 ноября 1993 года липецкий облсовет по инициативе Королёва руководствовался указаниями вице-президента А. В. Руцкого и постановлениями Верховного Совета Российской Федерации.
В ноябре 1993 года Королёв был избран депутатом Совета Федерации I созыва, получив 27,4 % голосов (всего в округе баллотировалось 5 кандидатов). Входил в состав комитета по бюджету и финансам, впоследствии — комитета по аграрной политике.
В январе 1996 года вошёл в состав Совета Федерации II созыва. По предложению Е. С. Строева был избран заместителем председателя Совета Федерации.
В 1997 году Российский биографический институт присвоил Королёву звание «человек года» в области политики.
В 2006 и 2008 годах региональное деловое издание «Экономика и жизнь — Черноземье» совместно с некоммерческой автономной организацией «Институт политического анализа и стратегий» признавали Королёва лучшим губернатором Центрально-Чернозёмного региона.
Почётный гражданин Липецка (2009).
12 апреля 1998 году на выборах главы администрации Липецкой области Королёв получил 79,38 % голосов. Действовавший до выборов глава областной администрации М. Т. Наролин набрал всего 13,81 % голосов. Избрание Королёва стало большой неожиданностью для политической и деловой элиты региона: несмотря на некоторые идеологические разногласия, Королёв считался «человеком Наролина». В 1993 году он работал в предвыборном штабе последнего, пользовался его покровительством. Руководство Новолипецкого металлургического комбината, ведущего предприятия области, обеспечивавшего до 25 % поступлений в областной бюджет, поддерживало на выборах обоих.
Поддержку Королёву на выборах оказал широкий спектр партий и движений: от леворадикального Союза офицеров Станислава Терехова до региональной организации «Яблоко» и «Монархического центра». Однако самой влиятельной силой в составе этого блока были коммунисты. КПРФ сняло своего кандидата в пользу Королёва, а лидер партии Г. А. Зюганов лично призывал избирателей голосовать за Королёва.
14 апреля 2002 году Королёв был переизбран на пост губернатора Липецкой области.
В 2005 году переутверждён на этой должности Президентом РФ В. В. Путиным.
22 апреля 2010 года Президент Российской Федерации Д. А. Медведев внёс на рассмотрение Липецкого областного Совета депутатов кандидатуру Олега Петровича Королёва для наделения его полномочиями главы администрации Липецкой области. 26 апреля депутаты Липецкого областного совета депутатов проголосовали за наделение Олега Королева полномочиями высшего должностного лица Липецкой области (49 — «за», 2 — «против»). 1 июня 2010 года официально вступил в должность главы администрации Липецкой области.
О. П. Королёв поддержал появившуюся в конце 1990-х годов идею переименования должности «губернатор Липецкой области» на «главу администрации Липецкой области». В регионах, где введены подобные посты, свою инициативу объясняют тем, что губерний в России нет.