Родился 18 января 1959 г. в Новосибирске.
В 1981 г. окончил физико-технический факультет Новосибирского электротехнического института (НЭТИ; ныне - Новосибирский государственный технический университет).
В вузе возглавлял комсомольский отряд дружинников.
В 1982—1984 гг. служил в Советской армии. Был командиром подразделения в радиотехнических войсках ПВО — начальником командно-технического узла.
В 1984—2003 гг. - работал в НИИ измерительных приборов: инженер, начальник сектора, ведущий инженер-конструктор. Предприятие, в частности, занималось разработкой электронно-вычислительной техники, системы ближней локации комплекса зенитной ракетной системы С-300.
В 1984 г. вступил в КПСС.
В феврале 1993 г. вошел в состав бюро Новосибирского обкома КПРФ. В 1994 г. стал вторым секретарем обкома КПРФ.
В декабре 1996 г. был избран в Новосибирский областной Совет депутатов в ходе довыборов, прошедших в Дзержинском районе Новосибирска.
В декабре 2000 г. стал депутатом Новосибирского городского совета III созыва. Возглавил фракцию КПРФ, куда входило 12 из 25 депутатов горсовета. Председателем совета, согласно уставу города, был мэр Новосибирска Владимир Городецкий.
В 2003-2014 гг. - депутат Государственной думы Федерального собрания РФ.
7 декабря 2003 г. был избран депутатом Государственной думы РФ IV созыва по Заельцовскому одномандатному избирательному округу №126 (Новосибирская область). Баллотировался от КПРФ, на выборах получил 24,5% голосов (второе место - Виктор Игнатов от "Зеленых", 15,31%). В Думе был заместителем председателя комитета по собственности. Входил в состав фракции КПРФ.
В феврале 2006 г. стал первым секретарем Новосибирского областного комитета КПРФ.
2 декабря 2007 г. избран депутатом Государственной думы V созыва по списку КПРФ в Новосибирской области (первый номер региональной группы №56, Заельцовская, Искитимская). Вошел в состав фракции коммунистов в Госдуме. Был членом комитета ГД по вопросам местного самоуправления, членом счетной комиссии. Входил также в комиссию Парламентского собрания Союза Белоруссии и России по экономической политике.
4 декабря 2011 г. вновь стал депутатом Госдумы РФ VI созыва от КПРФ. На выборах возглавлял региональную группу №51 от Новосибирской области. В Госдуме работал в комитете по федеративному устройству и вопросам местного самоуправления, являлся заместителем председателя комиссии Госдумы по правовому обеспечению развития организаций оборонно-промышленного комплекса РФ. Возглавлял комиссию по социальной политике, науке, культуре и гуманитарным вопросам Парламентского собрания Союза Белоруссии и России.
В 2014-2024 гг. - мэр Новосибирска.
Весной 2014 г. КПРФ выдвинула его кандидатуру на досрочные выборы мэра Новосибирска. Выборы были назначены после ухода с поста главы города Владимира Городецкого, назначенного вице-губернатором области (в 2014-2017 гг. - губернатор Новосибирской области). По итогам голосования 6 апреля 2014 г. Анатолий Локоть был избран мэром Новосибирска. Набрал 43,75% голосов, его ближайший соперник, единоросс Владимир Знатков, получил 39,57%. Всего в выборах участвовали 11 кандидатов. 23 апреля 2014 г. Анатолий Локоть официально вступил в должность мэра города.
С 27 мая 2017 г. - член президиума ЦК КПРФ.
В июне 2018 г. Локоть отказался от участия в выборах губернатора Новосибирской области в пользу Андрея Травникова ("Единая Россия"), занимавшего на тот момент должность врио главы региона. В сентябре 2018 г. Травников был избран руководителем области.
В единый день голосования 8 сентября 2019 г. вновь победил на выборах главы Новосибирска. За его кандидатуру проголосовали 50,25% избирателей (баллотировался от КПРФ). Второе место занял кандидат от ЛДПР Евгений Лебедев - 9,35%.
19 сентября 2021 г. был избран депутатом Государственной думы РФ VIII созыва по списку партии КПРФ. Баллотировался под первым номером в составе региональной группы №24 (Кемеровская, Новосибирская обл.). После избрания отказался от депутатского мандата.
В конце декабря 2023 г. стало известно, что Анатолий Локоть принял решение покинуть пост мэра Новосибирска по собственному желанию. Его полномочия были официально прекращены 25 января 2024 г.