Анатолій Колдаков народився у Тамані, де його батько будував завод, потім певний час жив у Херсоні та Запоріжжі. Батьки хлопця працювали на керівних посадах у текстильній промисловості. Школу майбутній форвард «Чорноморця» закінчував вже у Києві, де й визначився остаточно з тим, що хоче стати футболістом, не зважаючи на те, що займався й іншими видами спорту і навіть мав розряд з боксу. Через слабкий розвиток індустрії дитячо-юнацького футболу на той час, хлопець не мав можливості відвідувати ДЮСШ, шліфуючи свою майстерність спочатку в шкільній команді, а потім у армії.
Спочатку Анатолій служив у Вінниці, потім виступав за армійську команду в Кам'янці-Подільському, у складі якої й потрапив до Одеси на матч з місцевим «Торпедо». Саме той матч переглядав тренер «Чорноморця» Анатолій Зубрицький, якого вразила гра хлопця і він запропонував йому приєднатися до складу «моряків». Колдаков, маючи пропозиції й від інших команд, все ж вирішив обрати Одесу, ставши гравцем «Чорноморця».