Весной 1722 г. вместе с В. И. Генниным осматривал места и реки для проектирования Волго-Московского канала. Прибыл на Урал в 1722 г. в его команде.
В 1723 г. был один из основных участников строительства Исетского завода (Екатеринбурга). Капрал «за кондуктора» К. А. Гордеев активно участвовал в разметке и оформлении территории, составлении чертежей строений территории завода, строительстве крепости. Обследовал, а затем подготовил место под строительство плотины Полевского завода, координировал возведение крепости вокруг Багарякской слободы[55]. В этом же году составил план плотины и застройки Верхне-Уктусского завода. В 1723 г. получил ранг сержанта полевой артиллерии.
С ноября 1723 г. вместе с Н. Г. Клеопиным руководил деятельностью Сибирского обер-бергамта.
В 1724 г. пожалован в берггешворены.
Во второй половине 1725 г. К. А. Гордеев фактически возглавлял Сибирский обер-бергамт с первыми помощниками, комиссарами С. К. Нееловым и Ф. Е. Неклюдовым.
С октября 1725 г. К. А. Гордеев руководил строительством платного двора в Екатеринбурге. В декабре здесь начали чеканить первые деньги-платы.
6 января 1726 г. был командирован с первыми образцами плат в Санкт-Петербург, в Кабинет е. и. в., Сенат, Берг-коллегию.
В декабре 1726 г. был командирован с И. Г. Улихом на Полевской завод свидетельствовать качество добываемой руды.
В феврале-марте 1727 г. К. А. Гордеев разбирал тяжбу между Г. Замощиковым и компанейщиками Лобвинского завода.
С марта 1727 г. – глава Пермского бергамта. 15 июня 1727 г. получил чин гиттенфервальтера.
В 1728 г. в Екатеринбурге исполнял должность третьего члена Обер-бергамта.
В апреле 1729 г. руководил отправкой казенного каравана на Уткинской пристани. Она закончилась неудачей.
С марта 1730 по февраль 1732 г. вновь руководил Пермским бергамтом. В декабре 1730 г. отказался продлевать контракты иностранцам-специалистам В. Штифту, К. Клестлеру, Д. Келлеру, Я. Лоренсу, И. Лейксенринку, с чем не согласился В. И. Геннин.
С января 1732 г. – главный казначей Екатеринбургского завода.
С февраля по август 1732 г., согласно указу Сената, совместно с маркшейдерским учеником А. А. Татищевым, который должен был составлять ландкарты, и штейгером И. X. Лейксенринком обследовал и описал территории и рудники Восточной Сибири – и в частности, Колывано-Воскресенский завод.