«Между мысами Тархан-Кутом и Карамруном вдается бухта, не посещаемая по открытому своему положению. На берегу ея раскинута деревня Караджа с двумя мельницами и садом, а несколько южнее - Кордон». Так упоминается в Лоции Черного моря за 1851 год самое западное в Крыму село. Ныне оно носит название Оленевка, до 1945 года - Караджа. Расстояние от Черноморского до села 22 км.
     Местность на берегу Караджинской бухты Черного моря, о которой идет речь в Лоции, была заселена в глубокой древности. Находки археологов позволили сделать вывод о поселениях здесь человека эпохи энеолита (меднокаменного века) и ранней бронзы, датируемых III - II тысячелетиями до н. э. На северо-восточной окраине села Оленевка и в его окрестностях найдены остатки двух античных городищ, вероятно, входивших в состав херсонесской сельскохозяйственной хоры, а также скифского поселения. Есть предположение о, возможно, постоянном или временном пребывании в Западной Таврике древних росов. В пользу этого свидетельствует обозначение на древних портоланах (итальянских морских картах) поселений с названиями Icola Rossa, Rossico. Небезынтересно, что и на месте нынешнего поселка Черноморское в древности находилось городище Yarango Limmen, наименование которого некоторые ученые переводят на русский язык как «Гавань варягов». Возможно, она служила местом отдыха варягов и русичей во время их походов на Константинополь или предназначалась для постоянного проживания военных дружин росов (русичей) варяжского, славянского или какого-либо иного происхождения, занимавшихся мореплаванием и ратными делами.
     Правда, археологические исследования не подтверждают фактов постоянного обитания славянских племен на Тарханкуте. Но вопрос этот нельзя считать до конца изученным из-за эпизодичности раскопок.
      Не исключено, что близ нынешней Оленевки жили тюрки-азиаты, переселившиеся в Крым ориентировочно в VII веке н. э.
Раннесредневековые поселения погибли в начале X столетия с приходом в Крым кочевников-печенегов. Во время Крымского ханства (1449-1783) на месте нынешнего села Оленевка существовала ногайско-татарская деревня Караджа, точная дата возникновения которой неизвестна.
      Есть несколько версий происхождения названия Караджа. В переводе с тюркского языка оно означает «косуля».
     Вполне возможно, что именно здесь обитали эти красивые животные, давшие наименование местности и селу. По второй версии, название села могло произойти от имени его хозяина, который носил распространенное в Средневековье тюркское имя Караджа.
     В крымско-татарский период существовал особый вид налога - карадж, которым облагали немусульманское население. Не исключено, что именно оно и преобладало в этой части западного Крыма, откуда и произошло название деревни.
    В списке населенных пунктов Тарханского кадылыка (судебного округа) в «Камеральном описании Крыма 1784 года» встречается еще одно наименование села - Карагаджа; в уставной грамоте 1861 года упоминается третий вариант этого топонима - Тарханкут.