Река Утхолок впадает в Охотское море в 29 милях к северу от устья Коврана. Известна русским с конца XVII века. На "Чертеже вновь Камчадальские земли", составленном около 1700 года по данным Владимира Атласова, река помечена под названием Аккалан, на последующих картах, начала XVIII века она именуется Околок, Окалан, Еткола... В 1739 году С.П. Крашенинников записал два варианта написания: Утхолока и Окала-ваем, последний вариант несет в себе несомненное влияние корякского языка ("ваям" - по-корякски - река). На так называемой "Карте Ивана Львова" (около 1700г.) есть упоминание о острожке под названием Ултошной. На его месте возникло последнее ительменское селение Утхолок.
Мыс Утхолокский замыкает с юга бухту Квачину. Старорусское название - Утколоцкий Нос. Ительменское название (в транскрипции С.П. Крашенинникова) - Ксыбылгин. Мыс Утхолоцкий известен со времен первых русских походов на Камчатку, с конца XVII века. Первая геодезческая съемка мыса принята в 1743 году участником Второй Камчатской экспедиции мичманом В.А. Хметевским. Работы его были продолжены штурманским учеником Г.А. Измайловым 1776 году.
Детальная геодезическая съемка мыса осуществленна в 1849 году поручиком корпуса флотских штурманом А.М. Гавриловым.
