В 1894 году руководителем класса пейзажной живописи академии был назначен А. И. Куинджи, в прошлом ученик И. К. Айвазовского. Профессор Куинджи обратил внимание на пейзажные этюды Богаевского и перевёл его в свой класс.

Богаевский был захвачен новым своеобразным методом «обучения творчеству», какой ввёл Куинджи. Здесь нашла полную поддержку и признание его склонность к пейзажному искусству. В классе Куинджи не было обязательной для всех программы обучения, и он освободил Богаевского от ненавистного для него рисования натурщиков.

Развитие дарования Богаевского пошло очень быстро, и на конкурс в 1897 году он представил картину «В горах», хоть и написанную в духе работ своего учителя, но выполненную мастерски.

В письме к одному из феодосийских друзей Богаевский высказал свои настроения и мечты, навеянные копированием картины Судковского «Штиль», находившейся тогда в академическом музее. Передавая впечатление от картины, он писал:

«Должно быть, художник, который написал эту картину, долго сидел на берегу, сидел, может быть, час и два и всё прислушивался, что говорила ему эта спокойная и величавая природа, прислушивался к волнам, что плескались у его ног, и к самой тишине, и молчанию природы, которое иной раз душе больше говорит, чем иной мир звуков. И с сердцем, полным только что выслушанной музыки, художник пришёл в свою одинокую мастерскую, заперся в ней и стал проводить счастливейшие в своей жизни часы перед начатой картиной. Забыты были все огорчения и треволнения жизни, и всё искупалось блаженнейшими минутами творчества».

Уже самые ранние произведения Богаевского были посвящены изображению природы родных мест — пустынных берегов восточного Крыма, очертаниями и рельефом местности во многом напоминающими Италию и Грецию. Изучая природу прибрежной полосы восточного Крыма и следы жизни народов, обитавших в этих местах в древние времена, К. Ф. Богаевский многие годы пишет исторические крымские пейзажи.

В 1898 году А. И. Куинджи повёз своих учеников за границу. Они посетили Германию и Францию. На Богаевского самое сильное впечатление произвела живопись мюнхенских романтиков-символистов — Штука, Клингера и картины Бёклина.

Одной из ранних работ Богаевского была картина «Древняя крепость» (1902 год, Феодосийская картинная галерея), изображающая ночь на берегу моря.

С представлением о ночных маринах в те годы обычно были связаны картины летней ночи у живописных берегов с золотой лунной дорожкой, манящей вдаль, и ласковой волной, играющей среди прибрежных камней.

Богаевский сознательно отрешается от такого изображения ночи. Его картина несколько мрачновата. На ней — развалины древней крепости, венчающей прибрежные каменистые холмы, берег со стороны моря и холмы, закрывающие горизонт. Только узкая полоска неба над стенами создаёт впечатление пространства.

Так построены композиции многих ранних работ Богаевского. На картине «Ночь у моря» (1903 год, Саратовский художественный музей им. Радищева) вовсе нет неба. Крупные волны бьют о скалистый берег, в расщелинах которого гнездятся прижатые ветром к земле низкорослые узловатые деревья.

В творчестве Богаевского море часто сопутствовало живописным образам и органически входило в его композиции.

Уже в ранних произведениях «Древняя крепость», «Киммерия», «Город у моря» море бушует у подножия развалин древних замков и крепостных стен, как бы олицетворяя разрушительную стихию времени. Мертвенный лунный свет усиливает впечатление пустынности, покинутости, разорённости некогда богатых городов.

Характерна для этого периода картина «Берег моря» (1907 год, Третьяковская галерея), на которой изображена каменистая прибрежная местность, написанная со стороны моря в лунную ночь. В картине нет ни красивых гор, ни пышной растительности. Она привлекает не внешней красотой, а тонко переданным лунным светом, мягко сверкающим на волнах и скалистых берегах. Картина полна лирической грусти, усиленной безлюдностью изображённых мест.

Ранние работы Богаевского полны чувства одиночества и глубокой тоски.

Одним из наиболее выразительных произведений этого периода является картина «Замок у моря» (1903 год, местонахождение неизвестно). Сюжет картины очень прост: на приморском мысу грозно высятся развалины средневекового замка. Бурное море катит свои суровые волны к подножию его стен. Их чередование и однообразная ритмичность усиливают ощущение безлюдности и одиночества. В этой работе художник сумел ярче, чем в других, передать атмосферу пустынной, покинутой человеком земли.

В самой живописи ранних работ художника, тяжёлой по цвету, перегруженной красочным слоем, отражены длительные поиски новых форм для выражения волновавших его образов. Богаевский, видимо, стремился к широкому письму, лёгкому, быстрому «бегу кисти», о чём не раз писал своим друзьям. Но так как смолоду он отличался строгой взыскательностью, то результаты лёгкого письма его не удовлетворяли. Он заново по нескольку раз переписывал свои картины, работал над ними, пока кисть его не увязала в перегруженном, жирном красочном слое, и с трудом «дотягивал» свою работу до конца. Вместо широкого, лёгкого письма получалась тяжёлая, глухая живопись. Он всю жизнь мечтал о «моцартовской лёгкости воплощения», но живописное мастерство давалось ему трудно.

Богаевский почти никогда не был в полной мере удовлетворён результатами своего труда, часто огорчался и впадал в отчаяние; это как-то не вязалось с доверчивой, мягкой, жизнерадостной натурой художника. Повышенная требовательность к себе порой мешала Богаевскому, связывала его в работе, иногда даже подрывала веру в свои силы. Возможно, это происходило от сознания, что уровень его живописного мастерства не позволял ему во всей полноте воплотить свои творческие замыслы. Вот как рассказал он об этом в одном из писем М. А. Волошину в 1907 году:

«Всё это время я работаю маслом. Чем дальше, тем больше убеждаюсь, что масляная краска действительно убивает во мне свободу и порыв своей условщиной тона и мазка; она в конце концов опошляет всякую первоначальную хорошую задачу, замысел. Приходится всё время приноравливаться к ней. Масляная краска у меня покрывает точно дряблым телом скелет замысла, из неё уже не увидишь крепости и силы костей. Вот и сейчас я бьюсь над картинами; к каждой новой я приступаю в надежде побороть пошлость краски, но в работе незаметно она всё дальше и дальше втягивает тебя, как в болото, и картину пишешь уже не как свободный, а как раб какой-то… «и робкий путь склоняет прочь от цели». Что же делать? Заниматься офортом, как Вы советуете? Нужно, конечно, будет попробовать, но это уже когда я поеду в Питер и там ознакомлюсь несколько с этим делом. Масляную краску я всё-таки никогда не брошу. Всё мне кажется, что ею, при уменьи, можно будет больше сказать, чем офортом. А затем, я очень люблю большие, свободные пространства холста, такой простор в них я чувствую для себя. Большой холст для меня, как степь широкая, по которой без конца хочется скакать на коне вдаль…»

Терзаясь порой в мучительных творческих исканиях, Константин Фёдорович по многу раз переписывал свои картины.

Иногда, чтобы отвлечься, Богаевский оставлял кисть и занимался различными хозяйственными делами. Затем возвращался в мастерскую и со свежей головой продолжал трудиться у мольберта.

Однажды мы застали его на крыше своего дома с мастерком в руках и ведром извести — он ремонтировал черепичную кровлю; в другой раз — за рытьём ямы в углу двора (потом, дней через 12–15, там уже стояла новая, хорошо построенная им летняя кухня). Так как самочувствие у него в этот период было не очень хорошее, не ладилось с живописью, то он сетовал на материальные затруднения, стараясь скрыть истинную причину своих хозяйственных хлопот. У Константина Фёдоровича не было недостатка в средствах. При надобности он мог бы пригласить рабочих для мелкого ремонта своего дома, но он не делал этого, зная, что, отдохнув во время физического труда от творческого напряжения, возвратится в мастерскую с новыми силами.