С конца V в. до н. э. становится заметным стремление Спартокидов к территориальному расширению государства. Первым объектом их экспансии стал Нимфей, находившийся до этого в какой-то зависимости от Афин. Был ли он членом Афинского морского союза или афинский контроль над ним осуществлялся иным путем, сказать трудно (Жебелев С.А., 1935; Каллистов Д.П., 1949; 1950; Брашинский И.Б., 1955, 1963а; Шелов Д.Б., 1956а; Блаватская Т.В., 1959; Gajdukevič V.F., 1971), но особые интересы Афин в Нимфее сомнению не подлежат. Вероятно, афинский протекторат над Нимфеем установился еще около 410 г., со времени экспедиции Перикла в Понт Евксинский. Хотя флот Перикла вряд ли посетил порты Северного Причерноморья (Брашинский И.Б., 1958; 1963а), пребывание афинской эскадры на Черном море должно было отразиться на положении северочерноморских городов и может быть, вызвало то напряжение в отношениях между Афинами и Боспором, которое характерно, по мнению некоторых исследователей (Берзин Э.О., 1958; Блаватская Т.В., 1959), для второй половины V в. до н. э. Переход Нимфея в руки боспорских Спартокидов произошел в самом конце V в. до н. э. Обстоятельства этого перехода нам неизвестны.
Вслед за Нимфеем пришла очередь Феодосии. Ее присоединение к Боспору позволило бы Спартокидам не только устранить торгового конкурента, но и овладеть превосходной феодосийской гаванью. С завоеванием Феодосии и ее округи вся территория Восточного Крыма оказалась бы в руках Спартокидов и граница государства на западе проходила бы по самой узкой части Керченского полуострова. Возможно, что в борьбе против Феодосии некоторую роль играли и политические мотивы: сохранилось предание, что в Феодосии жили какие-то боспорские изгнанники (Жебелев С.А., 1953, с. 168 сл.). Войну против Феодосии начал преемник Спартока I — Сатир I. Но феодосийцы оказали упорное сопротивление, на помощь им пришла Гераклея Понтийская, вероятно, опасавшаяся экспансии Боспора, угрожавшей только что основанной гераклейской колонии — Херсонесу.
Борьба затянулась на многие годы. В ходе этой борьбы умер Сатир I и лишь его сыну Левкону I (389–349 гг.), вероятно, в 80-х годах IV в., удалось подчинить Феодосию. Город был лишен самостоятельности, он потерял право чеканить собственную монету, а Левкон стал носить титул архонта Боспора и Феодосии. В дальнейшем, в IV и III вв. до н. э. феодосийцы, пользуясь различными военными затруднениями Спартокидов, несколько раз пытались вернуть себе независимость, но безуспешно (Шелов Д.Б., 1950).
При Левконе I происходит и значительное расширение Боспорского государства на востоке. Раньше всего была присоединена к Боспору Синдика, область очень сильно эллинизованная и находившаяся в тесной связи с Боспором еще в V в. до н. э. (Блаватская Т.В., 1959; Анфимов Н.В., 1963; Крушкол Ю.С., 1971). Рассказ Полиена (VIII, 59) о синдском царе Гекатее и царице Тиргатао позволяет предполагать, что овладение Синдикой произошло в результате длительной дипломатической борьбы, интриг и военных столкновений (Берзин Э.О., 1958; Блаватская Т.В., 1959; Устинова В.А., 1966). Затем Левкон подчиняет и другие меотские племена Прикубанья и восточного Приазовья. Как происходило это подчинение, мы не знаем, и о присоединении их земель к Боспору узнаем только из титулатуры Левкона, именуемого «архонтом Боспора и Феодосии, царем синдов, торетов, дандариев и исессов» (КБН, 6, 1037, 1038). Сын Левкона I Перисад I добавляет в свой титул названия племен фатеев и досхов или именуется просто царем всех меотов (КБН, 9-11, 971, 972, 1015, 1039, 1040). Видимо, в третьей четверти IV в. до н. э. процесс формирования территории Боспора был в основном завершен.